hdu 2412 Party at Hali-Bula

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意:人员之间形成一棵树,父节点是子节点的上司,现在选一些人,不能同时选上司和下属(是直属上司,再上几层的上司可以选),问最后能选多少人,在选的人数相同的情况下,选的方案是不是唯一的。
重新看这题已经是非常简单了,自底往上的更新即可,包括人数和唯一性,一并更新

  • dp[u][0]表示u子树下不选u点能得到的最大人数
  • dp[u][1]表示u子树下选u点能得到的最大人数
  • flag[u][0]表示在dp[u][0]的情况是否唯一,true唯一,false不唯一
  • flag[u][1]表示在dp[u][1]的情况是否唯一,true唯一,false不唯一

对于dp[u][1],因为选了u,所以u的儿子都不能选, dp[u][1] = sigma dp[v][0]; 如果有一个flag[v][0] = false; 那么 flag[u][1] = false;

对于dp[u][0],因为u没选,所以每个人儿子则可选可不选,那当然是选择较大的情况 dp[u][0] = sigma max(dp[v][0] , dp[v][1]);

那么出现了dp[v][0] = dp[v][1]; 那么就出现了不唯一,flag[u][0] = false;

那么选了dp[v][0],或者选了dp[v][1],但是flag[v][0] = false; 或 flag[v][1] = false;

那么flag[u][0] = false;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <string>
using namespace std;
#define N 210
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

vector<int>e[N];
int n,dp[N][2];
bool flag[N][2];
map<string,int>Map;

void dfs(int u,int fa){
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
dfs(v,u);
dp[u][1] += dp[v][0];
if(!flag[v][0]) flag[u][1] = false;
if(dp[v][0] > dp[v][1]){
dp[u][0] += dp[v][0];
if(!flag[v][0]) flag[u][0] = false;
}
else if(dp[v][1] > dp[v][0]){
dp[u][0] += dp[v][1];
if(!flag[v][1]) flag[u][0] = false;
}
else{
dp[u][0] += dp[v][0];
flag[u][0] = false;
}
}
dp[u][1]++;
}

int main(){
while(scanf("%d",&n)!=EOF && n){
int ID = 0; char name[110];
for(int i = 0; i <= n; i++)
e[i].clear();
Map.clear();
scanf("%s",name);
Map[name] = ++ID;
for(int i = 1; i < n; i++){
int u,v;
scanf("%s",name);
if(Map.find(name) == Map.end())
Map[name] = ++ID;
u = Map[name];
scanf("%s",name);
if(Map.find(name) == Map.end())
Map[name] = ++ID;
v = Map[name];
e[u].pb(v); e[v].pb(u);
}
cl(dp,0); cl(flag,true);
dfs(1,-1);
if(dp[1][0] > dp[1][1]){
printf("%d ",dp[1][0]);
puts(flag[1][0] ? "Yes" : "No");
}
else if(dp[1][1] > dp[1][0]){
printf("%d ",dp[1][1]);
puts(flag[1][1] ? "Yes" : "No");
}
else{
printf("%d %s\n",dp[1][1],"No");
}
}
return 0;
}