poj3342Party at Hali-Bula(树形dp)

简介:
 1 /*
 2    树形dp!
 3    判重思路:
 4    当dp[v][0]==dp[v][1]时,很自然,flag[u][0]必然是有两种方案的。flag[u][1]则不然,
 5    因为它只和dp[v][0]有关系。而若flag[v][0]不唯一时,则必然flag[u][1]也不唯一
 6    也就是u的子节点有dp[v][1]==dp[v][0](选与不选都一样),那么父节点u不选的时候一定会有
 7    多种方案!也就是flag[u][0]=false; 否则如果flag[v][0]==flase(子节点不选的时候有多种方案),
 8    那么父节点u选择的时候一定有多种方案,则flag[u][1]=false;
 9 */
10 #include<iostream>
11 #include<cstring>
12 #include<cstdio>
13 #include<string>
14 #include<map>
15 #include<algorithm>
16 #define N 205
17 using namespace std;
18 
19 map<string, int>mp;
20 int n;
21 int cnt;
22 int g[N][N];
23 int dp[N][2];
24 bool flag[N][2];
25 map<string, int>::iterator it;
26 
27 void dfs(int u){
28    for(int v=1; v<=n; ++v)
29        if(g[u][v]){
30           dfs(v);
31           dp[u][1]+=dp[v][0];
32           dp[u][0]+=max(dp[v][1], dp[v][0]);
33           if(dp[v][1]==dp[v][0]) flag[u][0]=false;
34           if(flag[v][0]==false) flag[u][1]=false;
35        } 
36 }
37 
38 int main(){
39    string na1, na2;
40    while(scanf("%d", &n) && n){
41        mp.clear();
42        memset(g, 0, sizeof(g));
43        cnt=0;
44        cin>>na1;
45        mp[na1]=++cnt;
46        for(int i=1; i<n; ++i){
47            dp[i][1]=1;
48            dp[i][0]=0;
49            flag[i][1]=flag[i][0]=true;
50            cin>>na1>>na2;
51            it=mp.find(na1);
52            if(it==mp.end())
53               mp[na1]=++cnt;
54            it=mp.find(na2);
55            if(it==mp.end())
56                mp[na2]=++cnt;
57            g[mp[na2]][mp[na1]]=1; 
58        }
59        dp[n][1]=1;
60        dp[n][0]=0;
61        flag[n][1]=flag[n][0]=true;
62        dfs(1); 
63        if(dp[1][1]>dp[1][0] && flag[1][1]) printf("%d %s\n", dp[1][1], "Yes");
64        else if(dp[1][0]>dp[1][1] && flag[1][0]) printf("%d %s\n", dp[1][0], "Yes");
65        else printf("%d %s\n", max(dp[1][0], dp[1][1]), "No");
66    }
67    return 0;
68 }









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3944702.html,如需转载请自行联系原作者
目录
相关文章
|
存储
poj 3254 Corn Fields (状态压缩dp)
状态压缩dp其实就是用二进制来表示所有的状态,比如这题, 我们在某一行可以这样取0 1 0 1 1 0 1,用1代表取了,0代表没取,因为这点,它的数据量也限制在20以内,所有看到这样数据量的题目可以先考虑一下状态压缩dp。对于有多行的数据,所有状态的总数必然很庞大,而且不用特殊的方法想要存储这些状态是不太现实的。既然每个点只有这两种情况,我们可以用二进制的一位来表示,0 1 0 1 1 0 1就可以表示为二进制0101101也就是十进制的45,如果我们想要枚举6个点的所有状态,我们只需要从0到2^6取其二进制就可以了,并不会重复或是多余。
32 0
|
5月前
【洛谷 P1219】[USACO1.5]八皇后 Checker Challenge 题解(深度优先搜索+回溯法)
**USACO1.5八皇后挑战**是关于在$n\times n$棋盘上放置棋子的,确保每行、每列及两条主对角线上各有一个且仅有一个棋子。给定$6$作为输入,输出前$3$个解及解的总数。例如,对于$6\times6$棋盘,正确输出应包括解的序列和总数。代码使用DFS解决,通过跟踪对角线占用状态避免冲突。当找到所有解时,显示前三个并计数。样例输入$6$产生输出为解的前三个排列和总数$4$。
38 0
hdoj 1520 Anniversary party(树形dp)
我们可以把一个节点当做一个人,每个节点都有一个权重。按照题目意思,如果我们取了某个节点,那么他的父节点和子节点都是不能取的。按要求选取节点,使得选取节点的权重和最大。
38 0
hdoj 1028/poj 2704 Pascal's Travels(记忆化搜索||dp)
有个小球,只能向右边或下边滚动,而且它下一步滚动的步数是它在当前点上的数字,如果是0表示进入一个死胡同。求它从左上角到右下角到路径数目。 注意, 题目给了提示了,要用64位的整数。
37 0
|
人工智能
poj 2299 Ultra-QuickSort 求逆序数 树状数组解法
所谓离散化,我们的了解就是对原数组排序,然后用所在位置的下标代替原数,这样我们就可以把数据范围缩小到1-500000,这个数组是开的下的。
44 0
|
存储 容器
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
145 0
|
网络架构
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
POJ 3250 Bad Hair Day、POJ 2796 Feel Good(单调栈)
HDU 3506 Monkey Party(动态规划)
HDU 3506 Monkey Party(动态规划)
59 0
HDU 3506 Monkey Party(动态规划)
POJ-Silver Cow Party (最短路)
POJ-Silver Cow Party (最短路)
98 0