#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100005;
int n, m, cnt;
int v[102], num[102], dp[maxn];
struct Queue {
int pos, val;
}q[maxn];
int main() {
while (~scanf("%d%d", &n, &m) && n && m) {
memset(dp, 0, sizeof(dp));
cnt = 0;
for (int i = 1; i <= n; i++)scanf("%d", &v[i]);
for (int i = 1; i <= n; i++) {
scanf("%d", &num[i]);
if (v[i] * num[i] >= m) { //大于背包容量相当于完全背包
for (int j = v[i]; j <= m; j++)
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
continue;
} //单调队列优化
for (int d = 0; d < v[i]; d++){ //枚举余数
int head = 1, rear = 0;
for (int j = 0; j <= (m - d) / v[i]; j++){
int cur = dp[j * v[i] + d] - j * v[i];
while (head <= rear && q[head].pos < j - num[i]) head++;
while (head <= rear && q[rear].val < cur) rear--;
q[++rear].val = cur;
q[rear].pos = j;
dp[j * v[i] + d] = q[head].val + j * v[i];
}
}
}
int ans = 0;
for (int i = 1; i <= m; i++)
if (dp[i] == i)ans++;
printf("%d\n", ans);
}
return 0;
}
标签:多重,背包,队列,int,maxn,dp,include,单调
From: https://www.cnblogs.com/WangBF/p/17737739.html