#include<stdio.h>#include<string.h>int v[61];int p[61];int q[61][2];int f[32001];int l[61];int main(){freopen("budget.in","r",stdin);//freopen("budget.out","w",stdout);int i,j;memset(q,0,sizeof(q));memset(v,0,sizeof(v));memset(p,0,sizeof(p));memset(f,0,sizeof(f));int N,m; //N表示总钱数,m表示物品个数scanf("%d %d",&N,&m);for(i=1;i<=m;i++){scanf("%d %d %d",&v[i],&p[i],&l[i]);// v表示价格,p表示重要度,q表示依附关系 if(l[i]) {if(q[l[i]][0]==0) q[l[i]][0]=i; else q[l[i]][1]=i;}} for(i=1;i<=m;i++){for(j=N;j>=1;j--){if(l[i]==0){if(j>=v[i]&&f[j-v[i]]+v[i]*p[i]>f[j]) f[j]=f[j-v[i]]+v[i]*p[i];if(j>=v[i]+v[q[i][0]]&&f[j-v[i]-v[q[i][0]]]+v[q[i][0]]*p[q[i][0]]>f[j]) f[j]=f[j-v[i]-v[q[i][0]]]+v[q[i][0]]*p[q[i][0]];if(j>=v[i]+v[q[i][1]]&&f[j-v[i]-v[q[i][1]]]+v[q[i][1]]*p[q[i][1]]>f[j]) f[j]=f[j-v[i]-v[q[i][1]]]+v[q[i][1]]*p[q[i][1]];if(j>=v[i]+v[q[i][1]]+v[q[i][2]]&&f[j-v[i]-v[q[i][0]]-v[q[i][1]]]+v[q[i][0]]*p[q[i][0]]+v[q[i][1]]*p[q[i][0]]>f[j]) f[j]=f[j-v[i]-v[q[i][0]]-v[q[i][1]]]+v[q[i][0]]*p[q[i][0]]+v[q[i][1]]*p[q[i][0]];}}}printf("%d",f[N]);return 0;}
/*状态转移方程f(j)=max{f[j], f[j-v[i]]+v[i]*p[i], f[j-v[i]-v[q[i][0]]+v[q[i][0]*p[q[i][0]], f[j-v[i]-v[q[i][1]]+v[q[i][1]*p[q[i][1]], f[j-v[i]-v[q[i][0]-v[q[i]][1]]+v[q[i][0]*p[q[i][0]]+v[q[i][1]]*p[q[i][0]] */
卤煮在OJ上的结果帮同样的数据在本地的结果不一样是什么情况……
并且只过了两个点……求教
/*状态转移方程f(j)=max{f[j], f[j-v[i]]+v[i]*p[i], f[j-v[i]-v[q[i][0]]+v[q[i][0]*p[q[i][0]], f[j-v[i]-v[q[i][1]]+v[q[i][1]*p[q[i][1]], f[j-v[i]-v[q[i][0]-v[q[i]][1]]+v[q[i][0]*p[q[i][0]]+v[q[i][1]]*p[q[i][0]] */
卤煮在OJ上的结果帮同样的数据在本地的结果不一样是什么情况……
并且只过了两个点……求教