[数据结构与算法]323. 战略游戏

树形dp，一般都是从叶子节点开始，所以一般和dfs相结合，这道题很静但，dp[i][1]表示以i为根节点并且选择i时的最少需要的士兵数，dp[i][0]表示以i为根节点并且不选择i时的最少需要的士兵数。递推公式也比较好写， dp[u][0]+=所有子节点dp[v][1]; dp[u][1]+=所有子节点min(dp[v][0],dp[v][1]);
添加链接描述

#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
const int M=1502,INF=0x3f;
vector<int>g[M];
int dp[M][2];
bool st[M];
void dfs(int u)
{
    //cout<<u<<endl;
    dp[u][1]=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        dfs(v);
        dp[u][0]+=dp[v][1];
        dp[u][1]+=min(dp[v][0],dp[v][1]);
    }
}
int main()
{
    int n;
    ios;
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        memset(st,false,sizeof(st));
        for(int i=0;i<n;i++)
        {
            int id;
            string s;
            cin>>s;
            int cur=0,cur1=0;
            while(cur<s.size()&&s[cur]!=':') cur++;
            id=stoi(s.substr(0,cur));
            while(cur<s.size()&&s[cur]!='(') cur++;
            cur1=++cur;
            while(cur1<s.size()&&s[cur1]!=')') cur1++;
            int num=stoi(s.substr(cur,cur1-cur));
            //cout<<id<<" "<<num<<endl;
            while(num--)
            {
                int t;
                cin>>t;
                g[id].push_back(t);
                st[t]=true;
            }
        }
        int root=0;
        while(st[root]==true) root++;
        //cout<<root<<endl;
        dfs(root);
        cout<<min(dp[root][0],dp[root][1])<<endl;
        for(int i=0;i<n;i++)
            g[i].clear();
    }
    return 0;
}