0%

P2016 战略游戏

题目链接

这道题其实就是一道简单的树形动态规划。

我们设状态$f[u][0/1]$为每个节点不放或者放士兵。则可以很容易得到状态转移方程:

  1. 当节点$u$不放士兵时,那么他的儿子节点就一定要放,$f[u][0]+=f[v][1]$。

  2. 当节点$u$放士兵时,那么他的儿子节点就可放可不放,那么$f[u][1]+=min(f[v][1],f[v][0])$。

    接下来就直接在回溯的时候转移状态,最后答案就是$min(f[1][0],f[1][1])$。

    #include<bits/stdc++.h>
    using namespace std;
    
    const int maxn=1510;
    int n,cnt=0,head[maxn],f[maxn][2];
    struct node{
        int n,v;
    }q[maxn*2];
    
    inline void add(int a,int b) {
        q[++cnt].n=head[a];
        q[cnt].v=b;
        head[a]=cnt;
    }
    void dfs(int u,int fa) {
        f[u][1]=1;
        for(int i=head[u];i;i=q[i].n) {
            int v=q[i].v;
            if(v==fa) continue;
            dfs(v,u);
            f[u][0]+=f[v][1];
            f[u][1]+=min(f[v][1],f[v][0]);
        }
    }
    
    int main() {
        cin>>n;
        for(int i=1;i<=n;i++) {
            int a,b,k;
            cin>>a>>k;
            for(int j=1;j<=k;j++) {
                cin>>b;
                add(a,b);add(b,a);
            }
        }
        dfs(1,-1);
        cout<<min(f[1][0],f[1][1])<<endl;
        return 0;
    }