P1064 金明的预算方案

2019-11-10 19:08:36

字体：大中小

来源：转载

供稿：网友

题见洛谷

由于依赖少，可以改为分组背包

#include<iostream>#include<cstdio>#include<cstring>#include<string> #include<algorithm>using namespace std;int v[210],c[210],n,m,wj[210][3],wpv[210],wpc[210]; int f[32000+10];bool p[210];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int vv,pp,QQ; scanf("%d%d%d",&vv,&pp,&qq); v[i]=vv;c[i]=vv*pp; if(qq==0) p[i]=true; else wj[qq][++wj[qq][0]]=i,p[qq]=true;//wj[qq][++wj[！ qq ！][0]]=i } int cnt=0,x=1; for(int i=1;i<=m;i++) { if(p[i]) { wpv[++cnt]=v[wj[i][1]]+v[i],wpc[cnt]=c[wj[i][1]]+c[i]; wpv[++cnt]=v[wj[i][2]]+v[i],wpc[cnt]=c[wj[i][2]]+c[i]; wpv[++cnt]=v[wj[i][1]]+v[wj[i][2]]+v[i],wpc[cnt]=c[wj[i][1]]+c[wj[i][2]]+c[i]; wpv[++cnt]=v[i],wpc[cnt]=c[i]; } }//将依赖背包拆成分组背包 for(int i=1;i<=cnt;i=i+4) { for(int j=n;j>=0;j--) for(int k=0;k<=3;k++) if(j>=wpv[i+k]) f[j]=max(f[j],f[j-wpv[i+k]]+wpc[i+k]); }//注释起的为第二种写法/* for(int i=1;i<=m;i++) { if(p[i]) { for(int j=n;j>=0;j--) { int x1=v[i],x2=v[wj[i][1]]+v[i],x3=v[i]+v[wj[i][2]],x4=v[i]+v[wj[i][1]]+v[wj[i][2]]; if(j>=x1) f[j]=max(f[j],f[j-x1]+c[i]); if(j>=x2) f[j]=max(f[j],f[j-x2]+c[i]+c[wj[i][1]]); if(j>=x3) f[j]=max(f[j],f[j-x3]+c[i]+c[wj[i][2]]); if(j>=x4) f[j]=max(f[j],f[j-x4]+c[i]+c[wj[i][1]]+c[wj[i][2]]); } } }*/ PRintf("%d",f[n]); return 0;}

上一篇：windows下查看软件的安装目录

下一篇：Codeforces Round #362 (Div. 2) A. Pineapple Incident（水题）