树上背包转移时,有些循环要正序,有些要倒序。但我在实际操作中一直对顺序问题想不清楚。
近日,看到一种转移方法:
void solve(int u,int fa)
{
for(int i=head[u];~i;i=edge[i].nxt)
{
int v=edge[i].to;
if(v==fa) continue;
solve(v,u);;
memset(flag,0,sizeof(flag));
for(int j=0;j<=min(siz[u],m);j++)
{
for(int k=0;k<=min(siz[v],m) && k+j<=m;k++)
{
flag[j+k]=max(flag[j+k],dp[u][j]+dp[v][k]+w);
}
}
}
for(int j=0;j<=m;j++)
{
dp[u][j]=flag[j];
}
}
通过一个临时的数组 flag 存放值,避免了因循环顺序造成的问题。
请问怎样写是否是正确的?如果是,在树上背包转移时是否通用,是否可以不再关心转移的顺序?