poj 3342 Party at Hali-Bula（树形DP+判断方式是不是唯一）

本文主要是介绍poj 3342 Party at Hali-Bula（树形DP+判断方式是不是唯一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、http://poj.org/problem?id=3342

2、题目大意：

现在要邀请n个人中的一些人参加晚宴，要求是有直接上下级关系的人不能同时出席，问最多可以邀请多少人参加，并判断在保证最大人数的情况下，人是不是唯一确定的

状态转移方程很好确定，难在怎么判断方案是不是唯一，假设第i个人参加时值最大，那么不能确定是不是不唯一，但是如果第i个人不去的方案最优的话，他的状态有两种，孩子要么去，要么不去，如果这两种状态的最大值相同，那么就是不唯一的，详见代码

3、题目：

Description

Input

Output

Sample Input

6
Jason
Jack Jason
Joe Jack
Jill Jason
John Jack
Jim Jill
2
Ming
Cho Ming
0

Sample Output

4 Yes
1 No

 

4、AC代码：

#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
vector<int> vec[205];
map<string,int> mp;
char str[205][105];
char tmp[105];
char a[105],b[105];
int dp[205][2];
int k;
int find(char a[105])
{for(int i=0; i<k; i++){if(strcmp(a,str[i])==0)return i;}strcpy(str[k++],a);return k-1;
}
void dfs(int root)
{for(int i=0; i<vec[root].size(); i++){int v=vec[root][i];dfs(v);dp[root][0]+=max(dp[v][0],dp[v][1]);dp[root][1]+=dp[v][0];}
}
int main()
{int n;while(scanf("%d",&n)!=EOF){if(n==0)break;k=0;mp.clear();scanf("%s",tmp);mp[tmp]=k++;for(int i=0; i<n; i++){vec[i].clear();dp[i][0]=0;dp[i][1]=1;}for(int i=1; i<n; i++){scanf("%s%s",a,b);if(mp.find(a)==mp.end()) mp[a]=k++;if(mp.find(b)==mp.end()) mp[b]=k++;vec[mp[b]].push_back(mp[a]);}dfs(0);//下面代码判断是不是唯一的方案int flag=1;for(int i=0; i<n; i++){if(dp[i][0]>dp[i][1]){for(int j=0; j<vec[i].size(); j++){int v=vec[i][j];if(dp[v][0]==dp[v][1]){flag=0;break;}}}if(flag==0)break;}if(flag==0 || dp[0][0]==dp[0][1])//注意判断条件，printf("%d No\n",max(dp[0][0],dp[0][1]));elseprintf("%d Yes\n",max(dp[0][0],dp[0][1]));}return 0;
}
/*
6
Jason
Jack Jason
Joe Jack
Jill Jason
John Jack
Jim Jill
2
Ming
Cho Ming
0
*/

5、AC代码,处理字符串用的for循环遍历的，没有用map

 

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
vector<int> vec[205];
char str[205][105];
char tmp[105];
char tmp1[105];
int dp[205][2];
int k;
int find(char a[105])
{for(int i=0; i<k; i++){if(strcmp(a,str[i])==0)return i;}strcpy(str[k++],a);return k-1;
}
void dfs(int root)
{for(int i=0; i<vec[root].size(); i++){int v=vec[root][i];dfs(v);dp[root][0]+=max(dp[v][0],dp[v][1]);dp[root][1]+=dp[v][0];}
}
int main()
{int n;while(scanf("%d",&n)!=EOF){if(n==0)break;k=0;scanf("%s",tmp);strcpy(str[k++],tmp);for(int i=0; i<n; i++){vec[i].clear();dp[i][0]=0;dp[i][1]=1;}for(int i=1; i<n; i++){scanf("%s%s",tmp,tmp1);int a=find(tmp);int b=find(tmp1);vec[b].push_back(a);}dfs(0);int flag=0;for(int i=0; i<n; i++){if(dp[i][0]>=dp[i][1]){for(int j=0; j<vec[i].size(); j++){int v=vec[i][j];if(dp[v][0]==dp[v][1]){flag=1;break;}}}if(flag==1)break;}if(flag==1 || dp[0][0]==dp[0][1])printf("%d No\n",max(dp[0][0],dp[0][1]));elseprintf("%d Yes\n",max(dp[0][0],dp[0][1]));}return 0;
}
/*
6
Jason
Jack Jason
Joe Jack
Jill Jason
John Jack
Jim Jill
2
Ming
Cho Ming
0
*/

 

 

这篇关于poj 3342 Party at Hali-Bula（树形DP+判断方式是不是唯一）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---