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] = 0dup[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 205char 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;}


分享给朋友:
您可能感兴趣的文章:
随机阅读: