请各位dalao指出这种做法的弊端, 本蒟蒻交上去是错误的
每次遇到附件就留出附件自身及其主件的空间,并加上它们的价值
#include<bits/stdc++.h>
using namespace std;
const int N=32005;
const int M=65;
int n,m,ans=0;
int dp[N];
int v[M],p[M],q[M];
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i)
scanf("%d%d%d",&v[i],&p[i],&q[i]);
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;++i)
for(int j=n;j>=v[i];--j){
if(q[i]==0)
dp[j]=max(dp[j],dp[j-v[i]]+v[i]*p[i]);
else if(j-v[i]-v[q[i]]>=0)
dp[j]=max(dp[j],dp[j-v[i]-v[q[i]]]+v[i]*p[i]+v[q[i]]*p[q[i]]);
}
for(int i=0;i<=n;++i)
ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
附赠数据:
输入:
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5
输出:
7430