我水平很菜,你忍一下。

题面

树形 DP。

首先可以发现, $m>2$ 时,难受度只出现在最大的头吃的果子上(因为我把果子分成最大的头吃的和其他的,其他的里面,相邻的果子让不同的头吃即可)。

然后我定义 $f_{i,j,k}$ 为当前为 $i$ 节点,当前节点分 $j$ 个果子给最大的头,当前节点选择情况为 $k$($1$ 选 $0$ 不选)。

那么对于每一个子节点,我们有
$$
f_{u,j,0}=\operatorname{min}\{ \operatorname{min}\{ f_{v,t,0}+f_{u,j-t,0}+[m=2]w_i,f_{v,t,1}+f_{u,j-t,0} \} \},\\
f_{u,j,1}=\operatorname{min}\{ \operatorname{min}\{ f_{v,t,1}+f_{u,j-t,1}+w_i,f_{v,t,0}+f_{u,j-t,1} \} \}
$$

解释:
当我当前节点不给最大头,那么 $f_{u,j-t}$ 的第三项只能取 $0$ ,同理,如果我当前节点不给最大头吃,那么 $f_{u,j-t}$ 的第三项只能取 $1$ 。

如果 $m=2$ ,那么当我当前节点和当前节点的子节点全部取 $0$ 时,就是说这两个点都给第二个头吃,那么答案要加上 $w_i$ ,否则不用(前面说过了)。

然后如果我当前节点和子节点全部给大头,那么这中间这段树枝必须加到答案里。

但是,这样做会导致更新过的 $f$ 再去更新别的 $f$ ,所以我们要把用来更新的 $f$ 拍到另一个数组 $g$ 中,则:
$$
f_{u,j,0}=\operatorname{min}\{ \operatorname{min}\{ f_{v,t,0}+g_{j-t,0}+[m=2]w_i,f_{v,t,1}+g_{j-t,0} \} \},\\
f_{u,j,1}=\operatorname{min}\{ \operatorname{min}\{ f_{v,t,1}+g_{j-t,1}+w_i,f_{v,t,0}+g_{j-t,1} \} \}
$$

这样方程就写完了。

另外,如果果子个数不够,那么答案就是 $-1$ 。

最终输出的答案就是 $f_{1,k,1}$ ,因为规定第一个点必须选。

代码

分类: 文章

Chiimo

菜.

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code