POJ1463-Strategic game-（树形dp）
http://poj.org/problem?id=1463
题意：有一棵n个结点的树，要在这棵树上放士兵守卫，一个士兵可以守卫自己所在的位置以及与之相邻的点。问最少放多少个士兵？
题解：对于每个点，两种情况，放与不放，放则计数1，不放则计数0。
对于某个点x
如果不放，则与他相邻的点必然要放，否则谁来守卫点x？
如果放，则与他相邻的点可放可不放。
首先要造一棵树，从根节点对所有儿子节点深搜。
dp[i][0]和dp[i][1]表示 包括i本身 和 以i为父节点的子孙结点的摆放数 的累计最小值。
对于样例1，可以造出如下这样的树，0是根结点，指向儿子。
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<math.h> 6 #include<string> 7 #include<map> 8 #include<queue> 9 #include<stack> 10 #include<set> 11 #define ll long long 12 #define inf 0x3f3f3f3f 13 using namespace std; 14 15 int n,m; 16 int dp[10086][2]; 17 vector<int>son[10086]; 18 bool vis[10086]; 19 20 void dfs(int x) 21 { 22 dp[x][0]=0; 23 dp[x][1]=1;///每次进入深搜，初始化这个点是可以选或者不选 24 for(int i=0;i<son[x].size();i++) 25 { 26 int y=son[x][i]; 27 dfs(y); 28 dp[x][0]+=dp[y][1]; ///如果不选，那么谁来守卫？那儿子就需要守卫 29 dp[x][1]+=min(dp[y][0],dp[y][1]);///如果选择守卫，则儿子可以选择守卫或者不守卫 30 } 31 } 32 33 int main() 34 { 35 while(scanf("%d",&n)!=EOF) 36 { 37 for(int i=0;i<n;i++) 38 son[i].clear(); 39 memset(vis,false,sizeof(vis)); 40 memset(dp,0,sizeof(dp)); 41 for(int i=0;i<n;i++) 42 { 43 int x,y; 44 scanf("%d:(%d)",&x,&m); 45 while(m--) 46 { 47 scanf("%d",&y); 48 son[x].push_back(y); 49 vis[y]=true;///y有父亲，不能作为根结点 50 } 51 } 52 for(int i=0;i<n;i++) 53 { 54 if(!vis[i])///找到没有儿子的结点作为根节点 55 { 56 dfs(i); 57 printf("%d ",min(dp[i][0],dp[i][1]));///取根节点的最小情况 58 break; 59 } 60 } 61 } 62 return 0; 63 }