我是星星 @ 2017-08-30 15:06:13
#include<iostream>
using namespace std;
int v[100],f[100][32001],k,r[100],p[100],o[100],n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>p[i]>>o[i]; //分别读入为物品i的价值,重要度,主件序号
}
k=n;
for(int i=1;i<=n;i++)
if(o[i])
if(r[o[i]]==0)
{
v[++k]=v[o[i]]+v[i];p[k]=p[o[i]]+p[i];r[o[i]]=i; //r[i]表示物件i的第一个附件的序号
v[i]=0;p[i]=0; //o[i]表示物件i的主件的序号
}
else
{
v[++k]=v[o[i]]+v[i]+v[r[o[i]]];p[k]=p[o[i]]+p[i]+p[r[o[i]]];
v[++k]=v[o[i]]+v[i];p[k]=p[o[i]]+p[i];
v[i]=0;p[i]=0;
}
for(int i=1;i<=k;i++)
for(int j=m;j>=1;j--)
if(v[i]<=j)
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*p[i]);
else f[i][j]=f[i-1][j];
cout<<f[k][m];
return 0;
}
求帮忙
by Out_Land @ 2017-08-30 16:42:26
在取时顺便计算值,选最优的
by Out_Land @ 2017-08-30 16:45:38
然后,状态转移方程.写的.可能.有点.多,不过很好写的~~~
by angleの奏 @ 2017-08-30 16:46:02
@2556937429lq 样例能过吗
by angleの奏 @ 2017-08-30 16:46:35
@2556937429lq 似乎发现了错误,但改了以后过不了样例
by angleの奏 @ 2017-08-30 16:47:10
@2556937429lq 还有你的r是什么
by Out_Land @ 2017-08-30 16:47:46
dalao出现!!
by Out_Land @ 2017-08-30 16:49:02
我一个小小蒟蒻还是跑吧(活捉大佬一位,逃)
by 我是星星 @ 2017-08-30 16:52:21
我给注释了r[i]表示物件i的第一个附件的序号
by angleの奏 @ 2017-08-30 16:53:18
哦
by 我是星星 @ 2017-08-30 16:55:12
还能改吗