本文主要是介绍POJ 3342 树形DP入门题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目意思和POJ2342一样，只是多加了一个条件，如果最大方案数唯一，输出Yes，不唯一输出No
dp的是时候多加一个变量记录答案是否唯一即可
#include "stdio.h"
#include "string.h"
#include "vector"
using namespace std;struct node
{int fa;vector<int>child;
}data[210];
struct comp
{int x,y; // x记录最优值，y记录最优值是否唯一
}dp[210][2];
int vis[210];void dfs(int cur)
{int i,next;vis[cur]=1;for (i=0;i<data[cur].child.size();i++){next=data[cur].child[i];if (vis[next]==0) dfs(next);dp[cur][1].x+=dp[next][0].x;if (dp[next][0].y==1) dp[cur][1].y=1;if (dp[next][0].x>dp[next][1].x){dp[cur][0].x+=dp[next][0].x;if (dp[next][0].y==1) dp[cur][0].y=1;}else if (dp[next][0].x<dp[next][1].x){dp[cur][0].x+=dp[next][1].x;if (dp[next][1].y==1) dp[cur][0].y=1;}else{dp[cur][0].x+=dp[next][1].x;dp[cur][0].y=1;}}
}
int main()
{int n,i,j,x,y,sum;char a[110],b[110],name[210][110];while (scanf("%d",&n)!=EOF){if (n==0) break;memset(vis,0,sizeof(vis));memset(dp,0,sizeof(dp));memset(data,0,sizeof(data));scanf("%s",name[1]);sum=1;for (i=2;i<=n;i++){scanf("%s%s",a,b);for (j=1;j<=sum;j++)if (strcmp(name[j],a)==0) break;x=j;if (j==sum+1){sum++;strcpy(name[sum],a);}for (j=1;j<=sum;j++)if (strcmp(name[j],b)==0) break;y=j;if (j==sum+1){sum++;strcpy(name[sum],b);}data[x].fa=y;data[y].child.push_back(x);}for (i=1;i<=sum;i++)dp[i][1].x=1;dfs(1);if (dp[1][1].x>dp[1][0].x){printf("%d ",dp[1][1].x);if (dp[1][1].y==0) printf("Yes\n");else printf("No\n");}else if (dp[1][1].x<dp[1][0].x){printf("%d ",dp[1][0].x);if (dp[1][0].y==0) printf("Yes\n");else printf("No\n");}else{printf("%d ",dp[1][0].x);printf("No\n");}}return 0;
}
这篇关于POJ 3342 树形DP入门题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
