LA 2038 Strategic game 树形DP .

题目地址：http://vjudge.net/problem/UVALive-2038
以前做过类似的题
就是，无根转有根
然后普通的DP
d[u][i] 表示u节点的父亲有没有被选中，i==1表示被选中，反之没有
为什么弄u的父节点呢，因为 如果弄u的节点信息，那么当u没被选中，子结点至少有一个要被选中，那么只能枚举被选中的那个，无法递推，有后效性

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=1500+5,INF=0x3f3f3f3f;
struct Edge
{int v,next;
}edges[maxn*2];
int head[maxn],tot;
int d[maxn][2];
void AddEdge(int u,int v){edges[tot]={v,head[u]};head[u]=tot++;
}
int DP(int u,int fa,int chose){int& ans=d[u][chose];if(ans!=-1) return ans;bool leaf=true;int C=1,NC=0; //选or不选for(int i=head[u];i!=-1;i=edges[i].next){int v=edges[i].v;if(v==fa) continue;leaf=false;C+=DP(v,u,1);  //选if(chose==1) NC+=DP(v,u,0);  //不选}if(leaf) ans=chose?0:1;  //叶子结点else {if(chose==1) ans=min(C,NC);else ans=C;}return ans;
}
int main(int argc, char const *argv[])
{int n;while(scanf("%d",&n)==1&&n){memset(head,-1,sizeof(head));tot=0;int m,u,v;REP(i,1,n){scanf("%d",&u);scanf(":(%d)",&m);while(m--){scanf("%d",&v);AddEdge(u,v);AddEdge(v,u);}}memset(d,-1,sizeof(d));printf("%d\n", DP(0,-1,1));}return 0;
}