AcWing 1077. 皇宫看守

题目传送门

一、算法分析

状态表示
\(f[i,0]\)：在点 \(i\) 不摆放警卫，且被父结点看到的所有摆放方案的最小花费

\(f[i,1]\)：在点 \(i\) 不摆放警卫，且被子结点看到的所有摆放方案的最小花费

\(f[i,2]\)：在点 \(i\) 摆放警卫的所有方案的最小花费

状态转移
\(f[i,0]=∑min(f[j,1],f[j,2])\)

\(f[i,2]=∑min(f[j,0],f[j,1],f[j,2])\)
\(f[i,1]=min(f[k,2]+\sum\limits_{j≠k}min(f[j,1],f[j,2]) )\)

注意：

计算\(f[i,1]\)时，先把所有儿子的\(min(f[j,1],f[j,2])\)的总和 \(sum\) 计算出来，当使用第 \(k\) 个儿子放警卫时，把第 \(k\) 个儿子的 \(min(f[k,1],f[k,2])\) 减去，便得到了 $\sum\limits_{j≠k}min(f[j,1],f[j,2]) $

二、实现代码

#include 

using namespace std;
const int INF = 0x3f3f3f3f;
/*
以下注释为早期笔记，希望对你有所帮助

状态机 + 树形Dp问题
状态表示:
    f(i, 0)：第i号结点被他的父结点安排的守卫看住的方案数
    f(i, 1)：第i号结点被他的子结点安排的守卫看住的方案数
    f(i, 2)：第i号结点自己安排守卫看住的方案数

状态计算:(j是i的子结点)
    f(i, 0) = sum{min(f(j,1), f(j,2))}
        i是被他父结点看住的，那他的子结点要么自己看自己，要么被自己的子结点看住
    f(i, 1) = min{w(k) + f(k, 2) + sum{min(f(j,1), f(j,2))}}
        i如果是被子结点看住的，那么枚举被子结点看住的所有方案，对所有方案求最小值
        这里的sum不包括j==k的情况，因此需要手动额外减去
    f(i, 2) = sum{min(f(j,0), f(j,1), f(j,2))} + w(u)
        i是被自己看住的，那他的子结点可以被父结点看住，可以自己看自己，也可以被自己的子结点看住
*/
const int N = 1510;
int n;
int h[N], w[N], e[N], ne[N], idx;
int f[N][3];
bool st[N];

//邻接表
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = INF; //f[u][1]求最小值，初始化为最大值
    f[u][2] = w[u];//初始化放置自己的代价

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        //u是被父结点看住，那么子结点j只能靠自己或靠自己的孩子
        f[u][0] += min(f[j][1], f[j][2]);
        //u自己看住自己，那么子结点j可以靠父节点，自己，子节点
        f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
    }

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        //f[u][0]中记录了sum{min(f(j,1), f(j,2))}，再从中减去对应的贡献即可得到remain ver
        f[u][1] = min(f[u][1], f[u][0] + f[j][2] - min(f[j][1], f[j][2]));
    }
}

int main() {
    //初始化邻接表
    memset(h, -1, sizeof h);
    cin >> n;
    //读入n个结点
    for (int i = 1; i <= n; i++) {
        int x, m;
        //结点号，费用，连接的点个数
        cin >> x >> w[x] >> m;
        while (m--) {
            int y;
            cin >> y;
            //建立有向图
            add(x, y);
            //标识不是根
            st[y] = true;
        }
    }
    //找到根
    int root = 1;
    while (st[root]) root++;
    //从根开始进行有向图的树形DP
    dfs(root);
    
    printf("%d\n", min(f[root][1], f[root][2]));
    return 0;
}