Another Crisis
UVA12186
定义：$dp[i]$为要使第$i$名员工向其上级发信最少需要多少工人，$DP(i)$返回$dp[i]$的值，$Son[i]$为第$i$名员工的所有直属下级。
每一个员工都只有一个直接上级，因此不会有两个工人由同一上级。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
using namespace std;
int N, T;
vector<int> Son[100001];
void Clear() {
for (int i = 0; i <= N; ++i) {
Son[i].clear();
}
}
bool Input() {
cin >> N >> T;
Clear();
if (!N && !T) {
return false;
}
for (int SonNode = 1; SonNode <= N; ++SonNode) {
int BossNode;
cin >> BossNode;
Son[BossNode].push_back(SonNode);
}
return true;
}
int DP(int ID) {
//如果该员工为工人，返回1（自己同意）
if (Son[ID].empty()) {
return 1;
}
int Len = Son[ID].size();
int* dp = new int[Len];
//求该员工的所有下属的dp值
for (int i = 0; i < Len; ++i) {
dp[i] = DP(Son[ID][i]);
}
//排个序
sort(dp, dp + Len);
//求该员工最少要至少多少下属同意
int&&LeastAgreeDirectReports = ceil(static_cast<double>(Len * T) / 100.);
int&& Ans = 0;
//选择所需工人数目最少的LeastAgreeDirectReports个下属，得到该员工对应的最少员工
for (int i = 0; i < LeastAgreeDirectReports; ++i) {
Ans += dp[i];
}
delete dp;
return Ans;
}
int main() {
while (Input()) {
cout << DP(0) << endl;
}
return 0;
}
