2 条题解
-
1zyx303 LV 7 @ 2018-05-27 11:52:21
补充楼下大佬 二进制优化过的代码
#include "bits/stdc++.h" using namespace std; int cont[10001],w[100001],c[100001],dp[10001]; int main() { int n,v; cin>>n>>v; for(int i=1;i<=n;i++) { scanf("%d%d%d",&c[i],&w[i],&cont[i]); } int nl=n; for(int i=1;i<=n;i++) { int x=1; while(cont[i]>x) { nl++; w[nl]=w[i]*x; c[nl]=c[i]*x; cont[i]-=x; x*=2; } w[i]=w[i]*cont[i]; c[i]=c[i]*cont[i]; } for(int i=1;i<=nl;i++) { for(int j=v;j>=c[i];j--) { dp[j]=max(dp[j],dp[j-c[i]]+w[i]); } } cout<<dp[v]; }
一定要注意数据有0个的情况!!!!!
-
12018-05-27 11:11:43@
无优化
#include"bits/stdc++.h" using namespace std; int v[10001]; int w[10001]; int s[1001]; int f[10001]; int main() { int n,m; cin>>n>>m; int i,j; int k; for(i=1;i<=n;i++) { scanf("%d%d%d",&v[i],&w[i],&s[i]); } for(i=1;i<=n;i++) { for(j=m;j>=0;j--) { for(k=1;k<=s[i];k++) { if(j<k*v[i])break; f[j]=max(f[j],f[j-k*v[i]]+k*w[i]); } } } cout<<f[m]; return 0; }
- 1
信息
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 84
- 已通过
- 18
- 通过率
- 21%
- 上传者