社区讨论

30分,知道错,不会改,求助

P1064[NOIP 2006 提高组] 金明的预算方案参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lw095mdm
此快照首次捕获于
2024/05/10 13:44
2 年前
此快照最后确认于
2024/05/10 17:51
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
int n,w,f[100005];
struct node{
	int jv,v,w,m,zhujiannum;
	bool b=0;
}a[100005];
using namespace std;
signed main()
{
	cin>>w>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].jv>>a[i].w>>a[i].m;
		a[i].v=a[i].jv*a[i].w;
		if(a[i].m==0)	a[i].zhujiannum=a[i].jv;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i].m==0)
			continue;
		else if(a[a[i].m].b==0)
		{
			a[a[i].m].zhujiannum+=a[i].jv;
			a[i].v+=a[a[i].m].v,a[i].jv+=a[a[i].m].jv;
			a[a[i].m].b=1;
			
		}
		else
			a[i].jv+=a[a[i].m].zhujiannum;
	}
//	for(int i=1;i<=n;i++)
//	{
//		cout<<a[i].jv<<' '<<a[i].v<<' '<<a[i].w<<' '<<a[i].m<<' '<<a[i].b<<' '<<a[i].zhujiannum<<endl;
//	}
	for(int i=1;i<=n;i++)
		for(int j=w;j>=a[i].jv;j--)
			f[j]=max(f[j],f[j-a[i].jv]+a[i].v);
	cout<<f[w];
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...