洛谷题单指南-树与图上的动态规划-P2016 战略游戏

原题链接：https://www.luogu.com.cn/problem/P2016

题意解读：在树中选择最少的节点，使得可以覆盖整个树，一个节点可以覆盖所有分支以及子节点。

解题思路：

1、状态表示

f[i][0]表示以i为根的子树且不选i的最少士兵数量，f[i][1]表示以i为根的子树且选i的最少士兵数量

2、状态转移

对于u的所有子节点v，

如果不选u，则子节点只能选，因此有f[u][0] += f[v][1]

如果选u，则子节点可以选或不选，因此有f[u][1] +=min(f[v][0], f[v][1])

3、初始值

f[u][0] =0

f[u][1] =1

4、答案

min(f[0][0], f[0][1])
100分代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2000;

vector<int> g[N];
int f[N][2]; // f[i][0]表示以i为根的子树且不选i的最少士兵数量，f[i][1]表示以i为根的子树且选i的最少士兵数量
int n;

void dfs(int u, int fa)
{
    f[u][0] = 0; //不选u时
    f[u][1] = 1; //选u时
    for(int v : g[u])
    {
        if(v == fa) continue; 
        dfs(v, u);
        f[u][0] += f[v][1]; //如果不选u，则子节点只能选
        f[u][1] += min(f[v][0], f[v][1]); //如果选u，则子节点可以选或不选
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) 
    {
        int u, k;
        cin >> u >> k;
        while(k--)
        {
            int v;
            cin >> v;
            g[u].push_back(v);
            g[v].push_back(u); //树要双向建边，任意点都能当做根节点
        }
    }
    dfs(0, -1); 
    cout << min(f[0][0], f[0][1]);
    return 0;
}