题解 P2458 【[SDOI2006]保安站岗】

搞完这题真的深有体会呀 状态：$dp[u][0/1/2]$ 含义 $dp[u][0]$，以**u**为根的子树中，节点**u**放置警察所需要的最小花费 $dp[u][1]$，以**u**为根的子树中，节点**u**不放置警察，但被父亲控制所需要的最小花费 $dp[u][2]$，以**u**为根的子树中，节点**u**不放置警察，但被儿子控制所需要的最小花费 状态转移方程： $dp[u][0]$：点**u**放置了警察。 所以首先应当花费该节点放置警察所需要的费用，记为$p[u]$，则$dp[u][0]$ 的初始值为$dp[u]$。而对于它的所有子节点**v**，**v**可以任何情况都可以满足要求，综上$dp[u][0] = p[u] + ∑_{v∈son(u)}min(dp[v][0] , dp[v][1] , dp[v][2])$ $dp[u][1]$：点**u**没有放置警察，但被父亲控制。 所以它的儿子不能选择被父亲控制这种情况，其它都可以选。故$dp[u][1] = ∑_{v∈son(u)}min(dp[v][0] , dp[v][2])$ $dp[u][2]$：点**u**没有放置警察，且目前未被任何节点控制。 所以**u**一定会被它的至少一个儿子控制，换句话来说，**u**的儿子中，至少有一个要放置警察。不妨设这个儿子为**x**，那么$dp[u][2]$的初始值应当为$dp[x][0]$，对于其它儿子依旧是除了无法选择被父亲控制这种状态其它都可以选。综上$dp[u][2] = dp[x][0] + ∑_{v∈son(u)≠x}min(dp[v][0] , dp[v][2])$ 那么现在的问题就是如何得到这个最优的**x**了，可以这么思考，如果**x**不是最优的，那么对于**x**来说，一定存在另一个子节点**y**满足 $dp[y][0] + ∑_{v∈son(u)≠y}min(dp[v][0] , dp[v][2]) < dp[x][0] + ∑_{v∈son(u)≠x}min(dp[v][0] , dp[v][2])$ 推得$dp[x][0] + ∑_{v∈son(u)≠x}min(dp[v][0] , dp[v][2]) - dp[y][0] - ∑_{v∈son(u)≠y}min(dp[v][0] , dp[v][2]) > 0$ 两式同时减去相同的部分，有$dp[x][0] + min(dp[y][0] , dp[y][2]) - dp[y][0] - min(dp[x][0] , dp[x][2]) > 0$ 即$dp[x][0] - min(dp[x][0] , dp[x][2]) > dp[y][0] - min(dp[y][0] , dp[y][2]) $ 所以对于最优的节点**x**，$dp[x][0] - min(dp[x][0] , dp[x][2])$一定是所有子节点中最小的。 另外写代码的时候要多考虑几个小地方，像什么初始值什么的。 ------------ ### Code ``` #include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int MAXN = 1500 + 5; int n , p[MAXN] , f[MAXN]; int rt , dp[MAXN][3]; bool hfa[MAXN]; vector <int> G[MAXN]; //0 有保安 ，1没保安但被父控制 ，2没保安未被控制 void dfs(int u) { int x = 0; dp[u][0] = p[u]; for(int i = 0 , v ; i < (int)G[u].size() ; ++i) { dfs(v = G[u][i]); dp[u][0] += min(min(dp[v][0] , dp[v][1]) , dp[v][2]); dp[u][1] += min(dp[v][0] , dp[v][2]); if((dp[x][0] - min(dp[x][0] , dp[x][2])) > dp[v][0] - min(dp[v][0] , dp[v][2])) x = v; } dp[u][2] = dp[x][0]; for(int i = 0 , v ; i < (int)G[u].size() ; ++i) { if((v = G[u][i]) == x) continue; dp[u][2] += min(dp[v][0] , dp[v][2]); } } int main() { dp[0][0] = 1 << 30; scanf("%d" , &n); for(int i = 1 , x , k , m , v ; i <= n ; ++i) { scanf("%d %d %d" , &x , &k , &m); p[x] = k; while(m--) { scanf("%d" , &v); hfa[v] = true; G[x].push_back(v); } } for(int i = 1 ; i <= n ; ++i) if(!hfa[i]){ rt = i; break; } dfs(rt); printf("%d\n" , min(dp[rt][0] , dp[rt][2])); return 0; } ```