记录编号 | 286831 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [NOIP 2006]金明的预算方案 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 0.015 s | ||
提交时间 | 2016-08-01 09:30:57 | 内存使用 | 0.48 MiB | ||
//经典的有依赖背包问题~~~~~ //这种题目的方法就是分类讨论, //首先假设只选主件,那么不就是一个简单的01背包吗?o(>﹏<)o //然后考虑选第一件附件,同上,只要在数组中多减一个附件就好了 // 然后选第二件。。。烦死了/(ㄒoㄒ)/~~ //最后就是同时选两件。。。一样,在f【】中同时减去两件的价格即可 //这样就大功告成了O(∩_∩)O~~ #include<cstdio> #include<algorithm> using namespace std; int w[70],p[70],q[70],f[50000]; //w表示价格,p表示重要度,q表示主见还是附件 int main() { freopen("budget.in","r",stdin); freopen("budget.out","w",stdout); int n,m; int l=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&w[i],&p[i],&q[i]); } for(int i=1;i<=m;i++) { int k1=0; int k2=0; int t1=0; int t2=0; if(q[i]==0) { for(int k=i+1;k<=m;k++) if(q[k]==i) { t1=k; k1=1; break; } for(int k=t1+1;k<=m;k++) if(q[k]==i) { t2=k; k2=1; break; } for(int j=n;j>=w[i];j--) { f[j]=max(f[j-w[i]]+w[i]*p[i],f[j]); f[j]=max(f[j-w[i]]+w[i]*p[i],f[j]); if((j-w[i]-w[t1])>=0&&k1==1) f[j]=max(f[j-w[i]-w[t1]]+w[i]*p[i]+w[t1]*p[t1],f[j]); if((j-w[i]-w[t2])>=0&&k2==1) f[j]=max(f[j-w[i]-w[t2]]+w[i]*p[i]+w[t2]*p[t2],f[j]); if((j-w[i]-w[t1]-w[t2])>=0&&k1==1&&k2==1) f[j]=max(f[j-w[i]-w[t1]-w[t2]]+w[i]*p[i]+w[t1]*p[t1]+w[t2]*p[t2],f[j]); } } } printf("%d\n",f[n]); return 0; }