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

Parabola

2018-12-08 15:51:45

题解

搞完这题真的深有体会呀

状态：dp[u][0/1/2]

含义

$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] = ∑_{v∈son(u)}min(dp[v][0] , dp[v][2])

所以**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;
}