poj1463(Strategic game 炒雞基礎樹dp)

題目

題意： 一個遊戲有n個點,在某些點上放置哨兵,每個哨兵可以監控和它有邊相連的點，問監視所有的點需要的最少的哨兵數.

dp[i][0]: 第i個點不放哨兵需要的以i為根節點的子樹最少需要的哨兵

dp[i][1]: 第i個點放哨兵需要的以i為根節點的子樹最少需要的哨兵

如果某一點不放哨兵,那麼他的子節點都需要設一個哨兵。

如果某一點放哨兵,那麼就從子節點放還是不放中選最小的.

#include<cstdio>
#include<iostream>
#include<cstring>
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N=1500+5,INF=0x3f3f3f3f;
struct Edge{int to,nex;}edge[N<<1];int head[N],tot;
inline void add(int from,int to){
    edge[++tot]=(Edge){to,head[from]},head[from]=tot;
    edge[++tot]=(Edge){from,head[to]},head[to]=tot;
}
int dp[N][2];
void dfs(int x,int fa){
    dp[x][0]=0,dp[x][1]=1;
    for(int i=head[x];i;i=edge[i].nex){
        int y=edge[i].to;
        if(y==fa) continue;
        dfs(y,x);
        dp[x][0]+=dp[y][1];
        dp[x][1]+=min(dp[y][0],dp[y][1]);
    }
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        m(head,0),tot=0;//m(dp,0);
        for(int i=1,x,num;i<=n;++i){
            scanf("%d:(%d)",&x,&num),++x;
            for(int j=1,y;j<=num;++j)
                scanf("%d",&y),++y,add(x,y);
        }
        dfs(1,1);
        printf("%d\n",min(dp[1][0],dp[1][1]));
    }
}