Vijos 1144 小胖守皇宫 解题报告

非常经典的皇宫守护问题，用树形DP即可求解。对于每个点的覆盖可以分三种情况讨论：

1. 在该点设守卫
2. 在子节点设守卫
3. 在父节点设守卫

分别用f[i,1],f[i,2],f[i,3]表示以上三种情况覆盖以该节点为根的子树所需的最少费用。则显然可以推出状态转移方程：

• f[i,1]=∑min(f[j,1],f[j,2],f[j,3])+v[i](j为i的子节点);
• f[i,2]=∑min(f[j,1],f[j,2])+mind(j为i的子节点;mind为所有子节点中f[j,1]-f[j,2]最小的，若存在f[j,1]<=f[j,2]则mind为0);对于叶节点，f[i,2]=v[i]。
• f[i,3]=∑f[j,2](j为i的子节点);

程序实现时用一个队列维护当前待处理的已经处理完全部叶节点的节点，最后加入队列中的节点就是根节点。

R1206607 Accepted 100 From IwfWcf－ P1144 FPC Vag 6K 2009-4-11 1:01:21

除非另有声明，本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。

Vijos 1180 选课 解题报告

以编号0为根进行TreeDP即可，由于是多叉树，所以采用资源分配型DP的方式转化为泛化背包来处理比较方便，注意由于根节点实际上是不存在的，故所求答案应为f[0,m+1]。

状态转移方程是f[father[now],i]=max(f[father[now],i],f[father[now],i-j]+f[now,j])(1<=i<=m+1,1<=j<i)，初始化f[i,1]=v[i]。

R1123578 Accepted 100 From IwfWcf－ P1180 FPC Vijos Dolphin 2009-1-26 10:57:35

ZJU/ZOJ 1134 Strategic Game 解题报告

题目大意是给出一颗树的节点连接关系，只需控制一个一个即可控制与其相邻的节点，问最少需要控制多少节点才能控制整棵树。

很容易抽象出题目的模型是图的最小顶点覆盖问题，对于一般图而言，这一问题是NP问题。但注意到问题的图非常特殊，是树结构，因此很容易想到树形DP。状态转移方程非常简单f[i,0]=∑f[j,1];f[i,1]=1+∑min(f[j,0],f[j,1]);其中f[i,0]表示对于以节点i为根的子树而言，如果不控制节点i，控制整棵子树最少需要控制的节点数；f[i,1]表示对于以节点i为根的子树而言，如果控制节点i，控制整棵子树最少需要控制的节点数。j是i的儿子节点。边界条件为f[k,0]=0;f[k,1]=1，k是叶节点编号。

1646711    2008-09-18 22:35:01     Accepted    1134    FPC    150    440    IwfWcf

ZJU/ZOJ 2013 Labyrinth 解题报告

题目大意是在一个矩阵中寻找最长的连续'.’序列的长度。任意两个'.’之间必定存在恰好一条路径。

由“任意两个'.’之间必定存在恰好一条路径”可知这幅图可以转化为树的形式，而题目所求极为树中的最长路。任取一个节点作为根，对树进行一次BFS遍历找到距离其最远的点，再从这个点开始对图进行一次BFS遍历，距离其最远的点与其之间的距离即为树的最长路。或者用TreeDP的形式求其最长的两颗子树的长度之和亦可。

3014581 2008-07-30 20:49:21 Accepted 2013 FPC 00:00.94 6268K IwfWcf@LZOI