求问
查看原帖
求问
779456
liaochengrui楼主2024/7/18 15:30

请各位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

2024/7/18 15:30
加载中...