第二种情况下,j>原来的sum,后面的式子是没有意义的.所以会WA
by SofanHe @ 2018-03-17 20:28:36
@[多功能的荀彧](/space/show?uid=43931) 但我是用现在的sum、j和子树的数据更新原来的dp数组啊，为什么会没有意义呢？
by p_b_p_b @ 2018-03-20 17:24:20
```cpp
int dfs(int x)//WA了
{
if (x>n-m) return 1;
register int i,j,k,sum=0;
for (i=head[x];i;i=edge[i].nxt)
{
int sz=dfs(edge[i].t);
memset(tmp,0,sizeof(tmp));
for (j=0;j<=sum;j++) tmp[j]=dp[x][j];
sum+=sz;
for (j=1;j<=sum;j++)
for (k=1;k<=sz&&k<=j;k++)
dp[x][j]=max(dp[x][j],tmp[j-k]+dp[edge[i].t][k]-edge[i].w);
}
return sum;
}
```
k=1时,你的tmp[j-k]有意义吗?
by SofanHe @ 2018-03-20 17:27:07
@[p_b_p_b](/space/show?uid=76481) ↑
by SofanHe @ 2018-03-20 17:27:19
@[多功能的荀彧](/space/show?uid=43931) k=1时，原来遍历过的子树取（j-1）个用户，当前子树内取一个用户，再减去路的权值，取max，不就是j个用户时赚的钱的最大值吗？
请原谅我是个蒟蒻QAQ
by p_b_p_b @ 2018-03-20 21:05:08
@[p_b_p_b](/space/show?uid=76481) temp[j-1]在原始意义上是不应该存在的,因为没有j-1个用户
by SofanHe @ 2018-03-20 21:11:51
@[多功能的荀彧](/space/show?uid=43931) 哦！懂了！谢谢大佬！%%%
by p_b_p_b @ 2018-03-20 21:25:31
所以你的完全背包是怎么过的。。按理说应该倒序背包容量。。
by Starrydream @ 2018-10-24 19:55:51