RT。稍微用了一下我的原创卡常多重背包优化,妹想到直接AC。
加强一下数据吧……
#include <bits/stdc++.h>
using namespace std;
#define MAXN 101
long long n, v;
long long m[MAXN], w[MAXN], s[MAXN], f[40004];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> v;
for (int i=1; i<=n; i++) cin >> s[i] >> w[i] >> m[i];
for (int i=1; i<=n; i++){
for (int j=v; j>=0; j--){
for(int k=0; k<=min(m[i], j/w[i]); k++) f[j]=max(f[j], f[j-k*w[i]]+k*s[i]);
}
}
cout << f[v];
return 0;
}
(注:原多重背包模板的第三层循环中 k 的终止条件为 min{mi,wiW},现在改成了 min{mi,wij},也删除了一个判断)
最后再希望能加强一下数据,最好是能卡过这个代码的O2的数据。(最后一个点永远 907ms,应该很好改)