一个想法
查看原帖
一个想法
771342
bigtele楼主2022/11/16 20:41

没看题解之前 naive 的做法是:

f[u][i]f[u][i] 表示 uu 的子树内,建 ii 个伐木场时的最小花费。

g[u][i]g[u][i] 表示在 f[u][i]f[u][i] 的条件下还需要向上转移多少木料。

感觉挺对的,转移方程也写出来了:
f[u][i]=min(f[u][ij]+f[v][j]+g[v][j]×w)f[u][i] = \min(f[u][i-j]+f[v][j]+g[v][j]\times w)
然后找到一个满优的 jj
g[u][i]+=g[v][j]g[u][i] += g[v][j]

感觉也像树上背包,但我树上背包学的是一坨*,调不出来。这是我的代码。求大佬帮我看看,可以给报酬,谢谢!

2022/11/16 20:41
加载中...