HDU 1054 Strategic Game（树形dp）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1510;
 6 bool father[maxn];//父节点，判断一个子节点有没有父节点
 7 int brother[maxn];//兄弟节点，存入一个父节点下的多个节点
 8 int son[maxn];//存入子节点
 9 int dp[maxn][2];//dp，在这个节点选择放还是不放
10 int n,m,res,root; 
11 
12 void tree(int r){
13     dp[r][0]=0;//该节点不放哨兵 
14     dp[r][1]=1;//该节点放哨兵
15     int x=son[r];//x为该节点最后标记的子节点
16     while(x!=-1){ //只要还有子节点，继续 
17         tree(x);//纵向遍历该节点
18         dp[r][1]+=min(dp[x][0],dp[x][1]);//父节点放了，子节点可以选择放与不放
19         dp[r][0]+=dp[x][1];//父节点不放，子节点要放
20         x=brother[x];//横向遍历上一个兄弟节点 
21     } 
22 }
23 
24 int main(){
25     while(scanf("%d",&n)!=EOF){
26         int p,q;
27         memset(son,-1,sizeof(son));
28         memset(father,0,sizeof(father));
29         for(int i=1;i<=n;i++){
30             scanf("%d:(%d)",&p,&m);
31             for(int i=1;i<=m;i++){
32                 scanf("%d",&q);
33                 brother[q]=son[p];//同一个父节点的上一个兄弟 
34                 son[p]=q;//p的子节点是q，同时，如果m>1，输入的下一个q2的brother[q2]=q，实现之间的连接 
35                 father[q]=1;//标记q有父节点 
36             }
37         }
38         for(int i=0;i<n;i++){
39             if(!father[i]){//如果i没有父节点，那i就是根节点 
40                 root=i;//标记i为根节点 
41                 break;
42             }
43         }
44         tree(root);
45         res=min(dp[root][1],dp[root][0]);
46         printf("%d\n",res); 
47     }
48     return 0;
49 }