求助·关于树上背包的两种写法

这是第一种写法，样例能过但是全 WA，dp 的定义是

f[u][j]

表示以

u

为根的子树，包含

u

，体积不超过

j

，能获得的最大价值是多少。

答案是

f[0][m]

。

CPP

void dfs(int u){
	f[u][0]=0;
	for(int j = wei[u];j<=m;++j){
		f[u][j] = max(f[u][j],val[u]);
	}
	for(auto v : g[u]){
		dfs(v);
		for(int j = m;j>=0;--j){ // 枚举 u 这个子树的体积
			for(int k = 0;k<=j;++k){ // 枚举 u 一棵子树用的体积
				f[u][j] = max(f[u][j],f[u][j - k] + f[v][k]);
			}
		}
	}
}

然后我看完题解，换了另外一种状态

f[u][j]

表示以

u

为根的子树，不包含

u

，体积不超过

j

时能获得的最大价值。然后就过了，我也没弄明白这两个之间的差异在哪里

CPP

void dfs(int u){
	f[u][0]=0;
	for(int j = wei[u];j<=m;++j){
		f[u][j] = val[u];
	}
	for(auto v : g[u]){
		dfs(v);
		for(int j = m - wei[u];j>=0;--j){ // 枚举 u 这个子树的体积
			for(int k = 0;k<=j;++k){ // 枚举 u 一棵子树用的体积
				f[u][j + wei[u]] = max(f[u][j + wei[u]],f[u][j + wei[u] - k] + f[v][k]);
			}
		}
	}
}

求助·关于树上背包的两种写法

讨论操作

回复

相关推荐

求助·关于树上背包的两种写法