- Quiz
- AC
- 解説
- tsutajさんのBlogを読んだ
- 各品物を1, 2, 4, 8個... に分解して、採用・非採用で分岐していけばmの箇所のオーダーはlog(m)になる
- 他は普通の荷持1個だけナップサックと同じ
- その他
- 蟻本に載っていそうで載っていなかった
- うしさんのライブラリではスライド最小値を使ってlogを消しているみたい
- 計算量
- N 種類数 (100)
- W 容量 (10000)
- m 選べる個数の最大値(10000)
- O(N W log m) = 100 x 10000 x log(10000) = 1.5 x 107程度
int main(){
ll N,C;
cin>>N>>C;
VI V(N);
VI W(N);
VI M(N);
rep(i,N)cin>>V[i]>>W[i]>>M[i];
VI dp(C+1,-1);
dp[0]=0;
rep(i,N){
ll m = M[i];
rep(j,15){
ll num = 1<<j;
num = min(num, m);
if(num==0) break;
for(int w=C-1; w>=0; w--){
if(dp[w]==-1)continue;
if(w+W[i]*num<=C){
chmax(dp[w+W[i]*num], dp[w] + V[i]*num);
}
}
m -= num;
}
}
ll ma = 0;
rep(w,C+1){
chmax(ma, dp[w]);
}
p(ma);
return 0;
}