uva 12186 Another Crisis

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

树dp

题意:给一个有根树,0是最大的boss,依次下去是人员组成的等级关系,叶子就是工人。在叶子开始给上级发信,当一个人收到了它的直属下属的信达到一定数量的时候,他要被迫向上级发信。问最后0这个大boss能收到信的话,一开始最少需要多少工人发信。一定数量是指一个百分比T,如果T=50,一个人有4个直属下属,至少需要2人发信,他才会向上级发信,如果T=60,那么需要3人发信。

简单的树dp,dp[u]表示会向上级发信所需要的最少工人数。如果u有多个直属下属v,先算百分比,得到至少需要num个下属发现,那么得到最小的前num个dp[v],累加起来就是dp[u]的值

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define N 100010
#define pb push_back

int n,p,dp[N];
vector<int>e[N];

void dfs(int u){
if(e[u].size() == 0){
dp[u] = 1; return ;
}
dp[u] = 0;
int num = (int)ceil(1.00*e[u].size()*p/100.00);
vector<int>t;
t.clear();
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
dfs(v);
t.pb(dp[v]);
}
sort(t.begin(),t.end());
for(int i = 0; i < num; i++)
dp[u] += t[i];
}

int main(){
while(scanf("%d%d",&n,&p)!=EOF){
if(n == 0 && p == 0) break;
for(int i = 0 ; i <= n; i++)
e[i].clear();
for(int i = 1; i <= n; i++){
int u;
scanf("%d",&u);
e[u].pb(i);
}
dfs(0);
printf("%d\n",dp[0]);
}
return 0;
}