社区讨论

关于树上背包转移的一个疑问

学术版参与者 7已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@lo7m0m2w
此快照首次捕获于
2023/10/27 04:01
2 年前
此快照最后确认于
2023/10/27 04:01
2 年前
查看原帖
树上背包转移时,有些循环要正序,有些要倒序。但我在实际操作中一直对顺序问题想不清楚。
近日,看到一种转移方法:
CPP
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 存放值,避免了因循环顺序造成的问题。
请问怎样写是否是正确的?如果是,在树上背包转移时是否通用,是否可以不再关心转移的顺序?

回复

12 条回复,欢迎继续交流。

正在加载回复...