自动搬运

查看原文

来自洛谷，原作者为

	xuxinyu 这个家伙不懒，但她就是啥也没留下

搬运于2025-08-24 21:47:10，当前版本为作者最后更新于2018-03-11 17:17:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

假设当前到了x的子树，现在是合并 x的第k个子树

f[x][j] 表示x的前k-1个子树该覆盖的完全覆盖，而且还能向上覆盖j层的最小代价

这个向上是针对x来说的，即可以向x的祖先方向再覆盖j层

对于第k个子树的意义就是，兄弟子树放置的守卫可以帮x的第k个子树覆盖前j层（第1层为x的子节点）

那么相应的就要有一个状态来表示这个 可以让兄弟子树 帮忙覆盖 的前j层

g[x][j] 表示还需要覆盖x的前k个子树中的前j层，且第j层以下该覆盖的完全覆盖（第1层为x）的最小代价

状态转移：

设x的第k个子节点为y

向x的上方覆盖j层，只需要x的子节点中有一个子节点z能向上覆盖j+1层 即可

所以f的转移有两种：z是前k-1个子节点中的，z是第k个子节点

f[x][j]=min（f[x][j]+g[y][j] ，f[y][j+1]+g[x][j+1]）

g[x][j]+=g[y][j-1]

但是有可能x 再向上恰好覆盖j层的代价要小于再向上恰好覆盖j-1层的代价

即覆盖的更多代价反而要小

所以将f的状态定义改为 向上覆盖至少j层的最小代价

同理，g的状态定义改为还需要覆盖至多j层的最小代价

对f[x][]做一个后缀最小值，g[x][]做一个前缀最小值

代码http://www.cnblogs.com/TheRoadToTheGold/p/8544819.html