ryarrn @ 2018-11-05 18:21:53
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct hh
{
int v,p,f[5];
}a[60+5];
int n,mon,ans,maxn;
int dp[32000+5],cnt;
int main()
{
cin>>mon>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].v>>a[i].p>>a[i].f[0];
if(a[i].f[0]!=0)
{
if(a[a[i].f[0]].f[++cnt]==0)
a[a[i].f[0]].f[cnt]=i;
else a[a[i].f[0]].f[++cnt]=i;
cnt=0;
}
}
for(int j=1;j<=n;j++)
{
if(a[j].f[0]!=0)
continue;
for(int i=mon;i>=0;i-=100)
{
if(a[j].v<=i)
{
dp[i]=max(dp[i],dp[i-a[j].v]+a[j].v*a[j].p);
maxn=max(dp[i],maxn);
if(a[j].f[++cnt]!=0&&i+a[a[j].f[cnt]].v <=mon)
{
dp[i+a[a[j].f[cnt]].v]=max(dp[i],dp[i]+a[a[j].f[cnt]].v*a[a[j].f[cnt]].p);
maxn=max(dp[i+a[a[j].f[cnt]].v],maxn);
}
if(a[j].f[++cnt]!=0&&i+a[a[j].f[cnt]].v <=mon)
{
dp[i+a[a[j].f[++cnt]].v]=max(dp[i],dp[i]+a[a[j].f[cnt]].v*a[a[j].f[cnt]].p);
maxn=max(dp[i+a[a[j].f[cnt]].v],maxn);
}
if(a[j].f[2]!=0&&a[j].f[1]!=0&&i+a[a[j].f[1]].v +a[a[j].f[2]].v <=mon)
{
dp[i+a[a[j].f[1]].v+a[a[j].f[2]].v]=dp[i]+a[a[j].f[2]].v*a[a[j].f[2]].p+a[a[j].f[1]].v*a[a[j].f[1]].p;
maxn=max(dp[i+a[a[j].f[1]].v+a[a[j].f[2]].v],maxn);
}
cnt=0;
}
}
}
// for(int i=100;i<=mon;i+=100)
// {
// cout<<dp[i]<<" ";
// }
cout<<maxn;
return 0;
}
by ryarrn @ 2018-11-05 18:23:25
测试数据的第一个我的c++和洛谷ide输出就不一样,求大佬解答
by ryarrn @ 2018-11-05 20:56:35
@chen_zhe 大佬可以帮忙看看吗