【刷题】动态规划——树形DP：皇宫看守

题目链接

战略游戏的加强版，只要保证每个点自身被选或其相邻的点被选就可以。

由于相邻的点包括父亲和孩子，所以只考虑孩子状态不够，还要考虑父亲，因此设3个状态：

设当前结点是点$i$，孩子结点是$s_1,s_2,...,s_n$，父亲结点是$p$
1、f[i, 0]：$p$有守卫，那么$i$的孩子可以有守卫、也可以没有（状态1、2）；但是$i$没有守卫，也就是$i$孩子的父亲没有守卫（状态0不行）。
f[i, 0] = min(f[s1, 1], f[s1, 2]) + min(f[s2, 1], f[s2, 2]) + ... + min(f[sn, 1], f[sn, 2])
2、f[i, 1]：$i$有守卫，那么$i$的孩子什么状态都行
f[i, 1] = w[i] + min(f[s1,0],f[s1,1],f[s1,2]) + min(f[s2,0],f[s2,1],f[s2,2]) + ... + min(f[sn,0],f[sn,1],f[sn,2])
3、f[i, 2]：孩子之一有守卫，先枚举哪个孩子有守卫（状态1），然后其他孩子可以有守卫也可以没有（状态1、2）；但是$i$没有守卫，也就是$i$孩子的父亲没有守卫（状态0不行）。
f[i, 2] = Min{f[sk, 1] + min(f[s1,1], f[s1,2])+...+min(f[sj,1], f[sj,2]) +...+ min(f[sn,1], f[sn,2])} sj != sk。

#include <iostream>
#include <cstring>
using namespace std;const int N = 1505;
const int INF = 1e9;int n, f[N][3], val[N];
int nxt[N], lnk[N], head[N], idx;
bool is_son[N];void add(int a, int b) {lnk[idx] = b;nxt[idx] = head[a];head[a] = idx ++ ;
}void dfs(int node) {f[node][1] = val[node];for (int i = head[node]; i != -1; i = nxt[i]) {int son = lnk[i];dfs(son);f[node][0] += min(f[son][1], f[son][2]);f[node][1] += min(f[son][0], min(f[son][1], f[son][2]));}f[node][2] = INF;for (int i = head[node]; i != -1; i = nxt[i]) {int son1 = lnk[i];int t = f[son1][1];for (int j = head[node]; j != -1; j = nxt[j]) {int son2 = lnk[j];if (son2 == son1) continue;t += min(f[son2][1], f[son2][2]);}f[node][2] = min(f[node][2], t);}
}int main() {scanf("%d", &n);memset(head, -1, sizeof head);int a, b, k, m;for (int i = 1; i <= n; i ++ ) {scanf("%d%d%d", &a, &k, &m);val[a] = k;for (int j = 1; j <= m; j ++ ) {scanf("%d", &b);add(a, b);is_son[b] = 1;}}int root; for (int i = 1; i <= n; i ++ ) {if (!is_son[i]) root = i;}dfs(root);printf("%d\n", min(f[root][1], f[root][2]));return 0;
}

再看第三种情况：
3、f[i, 2]：孩子之一有守卫，先枚举哪个孩子有守卫（状态1），然后其他孩子可以有守卫也可以没有（状态1、2）；但是$i$没有守卫，也就是$i$孩子的父亲没有守卫（状态0不行）。
f[i, 2] = Min{f[sk, 1] + min(f[s1,1], f[s1,2])+...+min(f[sj,1], f[sj,2]) +...+ min(f[sn,1], f[sn,2])}，sj != sk。

其实第三种状态枚举的时候，不需要挨个求min(f[sj,1], f[sj,2])，可以先求个所有$s_j$的min(f[sj,1], f[sj,2])的和，再扣掉$s_k$的min(f[sk,1], f[sk,2])、加上f[sk,1]。
而所有$s_j$的min(f[sj,1], f[sj,2])的和就是f[i, 0]。

因此上面31~36行可改成下面的14行

void dfs(int node) {f[node][1] = val[node];for (int i = head[node]; i != -1; i = nxt[i]) {int son = lnk[i];dfs(son);f[node][0] += min(f[son][1], f[son][2]);f[node][1] += min(f[son][0], min(f[son][1], f[son][2]));}f[node][2] = INF;for (int i = head[node]; i != -1; i = nxt[i]) {int son = lnk[i];int t = f[node][0] - min(f[son][1], f[son][2]) + f[son][1];f[node][2] = min(f[node][2], t);}
}