bzoj 4007 [JLOI2015]战争调度

Posted by

[TOC]

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=4007

题解

要是暴力的话是$2^{2^{10}}$,果断超时。
可以发现对于一个节点,如果它的各级祖先的状态已经确定,它的左右子树的贡献是独立的。
于是我们可以dfs枚举从根节点到每一个叶节点路径上的不同状态,记录下来,在叶节点的时候统计贡献。
树型DP:设$f[i][j]$表示第$i$个节点所在子树中有$j$个平民。
dfs枚举一下状态,就可以这样转移:
状态转移方程:
$$ f[o][i+j]=max\{f[lc][i]+f[rc][j]\} $$
边界条件:当$o$为叶节点时,根据链上的状态统计贡献。
答案为$max\{f[o][i]\},\quad 0\leq i\leq m$。

代码

Leave a Reply

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