littlecyber @ 2020-08-01 13:23:58
有大佬能帮看看哪错了吗QAQ
#include <bits/stdc++.h>
#define memset(a,b) memset(a,b,sizeof(a))
#define maxn 60+5
#define maxm 32000+10
using namespace std;
vector<int> root;
int dp[maxn][maxm],v[maxn],w[maxn],idx;
int e[maxn],ne[maxn],h[maxn];
int n,m;
void add(int fa,int son){
e[idx]=son;
ne[idx]=h[fa];
h[fa]=idx;
idx++;
}
void dfs(int fa){
for(int i=h[fa];i!=-1;i=ne[i]){
if(h[e[i]]!=-1)
dfs(e[i]);
for(int j=n-w[fa];j>=0;j-=10)
for(int k=0;k<=j;k+=10)dp[fa][j]=max(dp[fa][j],dp[fa][j-k]+dp[e[i]][k]);//泛化背包
}
for(int j=n;j>=w[fa];j-=10)dp[fa][j]=dp[fa][j-w[fa]]+v[fa];//包含主件在内的所有取值可能
for(int j=0;j<w[fa];j+=10)dp[fa][j]=0;
}
int main()
{
memset(h,-1);
cin>>n>>m;int tp,ro;idx=0;
for(int i=0;i<m;i++){
cin>>w[i]>>tp>>ro;
v[i]=w[i]*tp;
if(ro)add(ro-1,i);
else root.push_back(i);
}
for(int i=0;i<root.size();i++)
//if(h[i]!=-1)
dfs(root[i]);
for(int i=0;i<root.size();i++){
int t=root[i];
for(int j=n;j>=0;j-=10){
//if(h[t]!=-1)
for(int k=0;k<=j;k+=10)dp[m][j]=max(dp[m][j],dp[m][j-k]+dp[t][k]);
//else dp[m][j]=max(dp[m][j],dp[m][j-w[t]]+v[t]);
}
cout<<root[i]<<" ";
}
cout<<dp[m][n];
return 0;
}
by 邱江坤 @ 2020-10-03 19:14:34
https://www.luogu.com.cn/record/39197417 看一下我这个泛化背包的写法
by 邱江坤 @ 2020-10-03 19:29:50
for(int j=n-w[fa];j>=0;j-=10)
我的代码是for (int j = cap; j >= items[r].w; --j)
for(int k=0;k<=j;k+=10)
我的代码是for (int k = 0; k <= j - items[r].w; ++k)
最后我的代码是
for (int j = cap; j >= items[r].w; --j) f[r][j] += items[r].v;
你很有可能是k那里写错了,加上j把自己绕晕了