社区讨论
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 条回复,欢迎继续交流。
正在加载回复...