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.zzzyk.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;
}
补充:软件开发 , C++ ,