社区讨论
关于树上背包转移的一个疑问
学术版参与者 7已保存回复 12
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 12 条
- 当前快照
- 1 份
- 快照标识符
- @lo7m0m2w
- 此快照首次捕获于
- 2023/10/27 04:01 2 年前
- 此快照最后确认于
- 2023/10/27 04:01 2 年前
树上背包转移时,有些循环要正序,有些要倒序。但我在实际操作中一直对顺序问题想不清楚。
近日,看到一种转移方法:
CPPvoid 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 存放值,避免了因循环顺序造成的问题。请问怎样写是否是正确的?如果是,在树上背包转移时是否通用,是否可以不再关心转移的顺序?
回复
共 12 条回复,欢迎继续交流。
正在加载回复...