Strategic game 题解

本题是树的最小点覆盖问题。
设想一个结点放士兵和不放士兵两种情况，如果放士兵，那它的孩子们放不放士兵都无所谓，如果不放士兵，那孩子们必须放士兵（否则将无法覆盖）

那么很容易想到状态转移方程：
dp[root][1]=1+ min(dp[son][1],dp[son][0])
dp[root][0]= dp[son][1]

本题注意事项：
1.直接用一个字符变量c，吃掉所有多余的括号等无关内容
2.多组输入，记得清空邻接表和dp数组
3.最终的答案是在根结点的（因为你是从叶子一路往上推）
4.由于问题求解的是最小答案，跟以往树形dp经典问题不同，本题在状态转移的时候应当取min的操作

以下是代码：

#include <iostream>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include <cmath>
#include <vector>
#include <sstream>
using namespace std;
const int N = 1550;
bool havepar[N];
vector <int> G[N];
string s;
int dp[N][2];
int Troot;
int n;
void init()
{
    for (int i = 0; i < n; i++)
    {
        G[i].clear();
    }
    memset(havepar, 0, sizeof(havepar));
    memset(dp, 0, sizeof(dp));
}
void dfs(int root)
{
    if (G[root].size() == 0)
    {
        dp[root][1] = 1;
        dp[root][0] = 0;
    }
    for (int i = 0; i < G[root].size(); i++)
    {
        int to = G[root][i];
        dfs(to);
        dp[root][1] += min(dp[to][1], dp[to][0]);
        dp[root][0] += dp[to][1];
    }
    dp[root][1] += 1;
}
int main()
{
    while (scanf("%d", &n) != EOF)
    {
        init();
        int u;
        int num;
        char c;
        for (int i = 0; i < n; i++) 
        {
            scanf("%d%c%c%d", &u, &c, &c, &num);
            scanf("%c", &c);
            while (num--)
            {
                int v;
                scanf("%c%d", &c, &v);
                havepar[v] = true;
                G[u].push_back(v);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (!havepar[i]) {
                dfs(i);
                Troot = i;
            }
        }
        printf("%d\n", min(dp[Troot][1], dp[Troot][0]));
    }
}