Java教程

洛谷P2458题解

本文主要是介绍洛谷P2458题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题面

和这个题很像,但是本题有一个花费而那一题没有,所以我们要把 \(f\) 数组开大一维。 \(f_{i,j}\) 表示节点 \(i\) 为根的子树在 \(i\) 点是 \(j\) 状态下的最小花费。 状态可以参照我的题解。
那一个题解写得很含糊,这里再讲一遍。
分三种状态:

  1. 让父亲覆盖自己;
  2. 自己覆盖自己;
  3. 儿子覆盖自己。

然后我们来考虑转移。
什么时候能让父亲覆盖自己呢?必定是儿子都已经被覆盖了。所以 \(f_{u,1}=\operatorname{min}\{f_{v,2},f_{v,3}\}\) 。
让自己覆盖自己的这个状态,不管儿子怎么折腾都可以选,所以 \(f_{u,1}=\operatorname{min}\{f_{v,1},f_{v,2},f_{v,3}\}\) 。
最难的是状态3。要保证至少有一个儿子是状态2,且所有儿子都不是状态1。那么我们先做 \(f_{u,3}=\operatorname{min}\{f_{v,2},f_{v,3}\}\) ,然后判断一下我选的是哪一个。如果我选了 \(f_{v,2}\) 那么万事大吉,否则我记录一下 \(f_{v,2}-f_{v,3}\) 的最小值,最后再加上这个值即可。

然后这个题就做完了,除了巨多的分类讨论以外没有什么难度。
代码

这篇关于洛谷P2458题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!