题目传送门
[题目大意]
有 $n-1$ 个城市和 $n$ 个乡村, 它们构成一个二叉树. 恰有一条公路和一条铁路通向每个城市, 没有道路通向乡村, 首都是编号为 1 的城市. 每个乡村有三个参数 $a,b,c$, 每个乡村的不方便值为 $c*(a+x)*(b+y)$, 其中 $x,y$ 分别代表这个乡村到首都要经过 $x$ 条未修缮的公路和 $y$ 条未修缮的铁路. 对于每个城市, 从通向它的两条路中选择一条修缮, 求每个乡村的不方便值的最小总和.
[思路分析]
树形 DP 安排上
$f[x][i][j]$ 表示从 $x$ 号节点到首都要经过 $i$ 条未修缮的公路和 $j$ 条未修缮的铁路, 其子树中的所有乡村节点的不方便值之和.
如果 $x$ 是乡村节点, 那么直接枚举 $i,j$ 求 $f[x][i][j]=c[x]*(a[x]+i)*(b[x]+j)$
如果 $x$ 是城市节点, 那么枚举是修缮公路还是铁路, 设 $lson$ 是通过个公路到达的子节点,$rson$ 是通过铁路到达的子节点, 转移方程为 $f[x][i][j]=min(f[lson][i+1][j]+f[rson][i][j],f[lson][i][j]+f[rson][i][j+1])$
最后的答案就是 $f[1][0][0]$
据说有方法可以优化一下空间? emmm 有空再看叭 QAQ
[代码实现]
来源: http://www.bubuko.com/infodetail-3213725.html