关于树上背包转移的一个疑问
查看原帖
关于树上背包转移的一个疑问
255077
麦克斯韦の妖楼主2022/11/6 19:06

树上背包转移时,有些循环要正序,有些要倒序。但我在实际操作中一直对顺序问题想不清楚。

近日,看到一种转移方法:

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 存放值,避免了因循环顺序造成的问题。

请问怎样写是否是正确的?如果是,在树上背包转移时是否通用,是否可以不再关心转移的顺序?

2022/11/6 19:06
加载中...