Strategic game策略游戏

POJ

题意:有一座城市，有很多道路将整个城市连起来，整体上看上去像一棵树.需要放置尽可能少的士兵，保卫树上所有的边.士兵只能放在节点上，但是却可以保卫所有与这个节点相邻的边.求最少需要放置的士兵数量?

分析:树的最大独立集问题,树形DP来做.设\(f[x][1/0]\)表示以x节点为根的子树中,x节点放/不放士兵的 最少需要放置士兵的数量.

设y是x的子节点,则,

\(f[x][0]+=f[y][1]\),x节点不放士兵,则x的所有子节点y都要放置士兵.

\(f[x][1]+=min(f[y][0],f[y][1])\),x节点放了士兵,则其子节点y可放可不放,取最优值.

初始化:\(f[x][0]=0,f[x][1]=1\)

目标:\(min(f[root][0],f[root][1])\)

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
   return s*w;
}
const int N=1505;
struct ppx{
    int num,son[N];
}a[N];
int bj[N],f[N][2];
inline void dp(int x){
    f[x][0]=0;f[x][1]=1;//初始化
    for(int i=1;i<=a[x].num;i++){
        int y=a[x].son[i];
        dp(y);//树形DP一般都是先往下走,再更新
        f[x][0]+=f[y][1];
        f[x][1]+=min(f[y][0],f[y][1]);
    }
}
int main(){
    int n;
    while(~(scanf("%d",&n))){
        memset(bj,0,sizeof(bj));//初始化
        for(int i=1,x;i<=n;i++){
            x=read();a[x].num=read();
            for(int j=1,y;j<=a[x].num;j++){
                y=read();a[x].son[j]=y;
                bj[y]++;
            }
        }
        int root=0;while(bj[root])root++;//找根
        dp(root);
        printf("%d\n",min(f[root][0],f[root][1]));
    }
    return 0;
}

Strategic game策略游戏

原文：https://www.cnblogs.com/PPXppx/p/10989868.html