1 条题解
-
0
区分不限次数与有限次数,先将有限次数限制到容量可容纳的数量,再二进制拆分;使用 long long 保存总价值。
#include <bits/stdc++.h> using namespace std; int main(){int cap,n;cin>>cap>>n;vector<long long>d(cap+1);while(n--){int w,count;long long value;cin>>w>>value>>count;if(count==0){for(int j=w;j<=cap;j++)d[j]=max(d[j],d[j-w]+value);}else{count=min(count,cap/w);for(int k=1;count;k*=2){int take=min(k,count);count-=take;int cost=take*w;for(int j=cap;j>=cost;j--)d[j]=max(d[j],d[j-cost]+take*value);}}}cout<<d[cap]<<"\n";}
- 1
信息
- ID
- 3945
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者