hdu 2412 Party at Hali-Bula
树形DP+一个判断。
题目大意：
n个人形成一个关系树，每个节点代表一个人，节点的根表示这个人的唯一的直接上司，只有根没有上司。要求选取一部分人出来，使得每2个人之间不能有直接的上下级的关系，
求最多能选多少个人出来，并且求出获得最大人数的选人方案是否唯一。
前半部分很容易求得，直接一个树形DP，后面的判断最优解是否唯一比较难搞。。
看了roba的ppt顿时恍然大悟。
§
新加一个状态
dup[i][j]，表示相应的dp[i][j]是否是唯一方案。
§对于叶子结点, dup[k][0] = dup[k][1] = 1.
§对于非叶子结点,
–对于i的任一儿子j，若(dp[j][0] > dp[j][1] 且 dup[j][0] == 0) 或 (dp[j][0] < dp[j][1] 且 dup[j][1] == 0) 或 (dp[j][0] == dp[j][1])，则dup[i][0] = 0
–
对于I的任一儿子j有dup[j][0] = 0, 则 dup[i][1]=0表示dp[i][1]不唯一;dup[i][1]=1表示dp[i][1]唯一；
dup[i][0]同上。
这样思路就很清晰了。
这个题如果是我出的话，我会加以改进，把字母的长度缩短，然后n稍微变大，这样前面需要用到字典树来查找。但是不知道n变大之后对dp的影响会不会很大，
会不会使程序超时我就不得而解了。
代码：
# include<stdio.h>
# include<string.h>
# include<stdlib.h>
# define N 205
char map[N][105];
struct node{
int from,to,next;
}edge[2*N];
int head[N],tol,visit[N],dp[N][2],dup[N][2];
void add(int a,int b)
{
edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++;
}
int max(int a,int b)
{
return a>b?a:b;
}
void dfs(int root)
{
int j,u;
dp[root][0]=0;
dp[root][1]=1;
dup[root][0]=1;
dup[root][1]=1;
for(j=head[root];j!=-1;j=edge[j].next)
{
u=edge[j].to;
dfs(u);
dp[root][0]+=max(dp[u][0],dp[u][1]);
dp[root][1]+=dp[u][0];
if(dp[u][0]>dp[u][1] && dp[u][0]==0) dup[root][0]=0;
else if(dp[u][1]>dp[u][0] && dp[u][1]==0) dup[root][0]=0;
else if(dp[u][0]==dp[u][1]) dup[root][0]=0;
if(dup[u][0]==0) dup[root][1]=0;
}
}
int main()
{
int i,j,n,k,ans1,ans2;
char str1[105],str2[105];
while(scanf("%d",&n)!=EOF && n)
{
scanf("%s",map[1]);
k=1;
memset(head,-1,sizeof(head));
tol=0;
for(i=1;i<n;i++)
{
scanf("%s%s",str1,str2);
ans1=ans2=-1;
for(j=1;j<=k;j++)
{
if(strcmp(str1,map[j])==0) ans1=j;
if(strcmp(str2,map[j])==0) ans2=j;
}
if(ans1==-1)
{
k++;
ans1=k;
strcpy(map[k],str1);
}
if(ans2==-1)
{
k++;
ans2=k;
strcpy(map[k],str2);
}
add(ans2,ans1);
}
memset(dp,0,sizeof(dp));
dfs(1);
if(dp[1][0]>dp[1][1] && dup[1][0]==1) printf("%d Yes\n",dp[1][0]);
else if(dp[1][1]>dp[1][0] && dup[1][1]==1) printf("%d Yes\n",dp[1][1]);
else printf("%d No\n",max(dp[1][0],dp[1][1]));
}
return 0;
}
推荐.NET配套的通用数据层ORM框架：CYQ.Data 通用数据层框架