hdu_1054-Strategic Game

[cpp] 
/**樹形DP，推出狀態轉移方程：
 *不選擇當前節點：
 *  dp[i][0] += dp[Node[i].son[j]][1];
 *選擇當前節點：（最後加上1（它本身））
 *  dp[i][1] += min(dp[Node[i].son[j]][1], dp[Node[i].son[j]][0])
 *葉子節點處理：www.2cto.com
 *  dp[][0] = 0, dp[][1] = 1
*/ 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
 
#define Y       1 
#define N       0 
#define MAX     1501 
 
struct node{ 
    int son[MAX]; 
    int son_count; 
}Node[MAX]; 
 
int dp[MAX][2]; 
 
void DFSTraverse(int current){ 
    if( !Node[current].son_count ) return ; 
    for(int i = 0; i < Node[current].son_count; i ++){ 
        DFSTraverse(Node[current].son[i]); 
        dp[current][N] += dp[Node[current].son[i]][Y]; 
        dp[current][Y] += min(dp[Node[current].son[i]][N], dp[Node[current].son[i]][Y]); 
    } 
    dp[current][Y] ++; 
} 
 
int main(){ 
    int cas, num, son_num, root; 
    while(~scanf("%d", &cas)){ 
        memset(dp, 0, sizeof(dp)); 
        for(int i = 0; i < cas; i ++){ 
            scanf("%d:(%d)", &num, &son_num); 
            if( !i ) root = num; 
            if( !son_num ) { 
                Node[num].son_count = 0; 
                dp[num][Y] = 1; dp[num][N] = 0; 
            } 
            else{ 
                Node[num].son_count = son_num; 
                for(int j = 0; j < son_num; j ++) 
                    scanf("%d", &Node[num].son[j]); 
            } 
        } 
        DFSTraverse(root); 
        printf("%d\n", min(dp[root][Y], dp[root][N])); 
    } 
    return 0; 
}