题意:有一个老板和n个员工,除了老板每个员工都有唯一的上司,老板编号为0,员工们为1-n,工人(没有下属的员工),要交一份请愿书,

但是不能跨级,当一个不是工人的员工接受到直系下属不少于T%的签字时,自己也会签字,并交给上级,问你最少有多少工人签字,才能让老板收到请愿书。

析:题意比较简单,也好理解,很明显是一个动态规划的题目,d(u)表示u给上级要发信至少需要多少工人签字。假设u有k个结点,那么至少要

c = (kT-1)/100 + 1个工人,然后把每个结点排序,找出最少的工人即可,挺简单的。

代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring> using namespace std;
const int maxn = 100000 + 10;
int dp[maxn], T, n; vector<int> sons[maxn];
int DP(int u){
if(sons[u].empty()) return 1; int k = sons[u].size();
vector<int> d;
for(int i = 0; i < k; ++i)
d.push_back(dp[sons[u][i]]);
sort(d.begin(), d.end()); int c = (k * T - 1) / 100 + 1;
int ans = 0;
for(int i = 0; i < c; ++i) ans += d[i];
return ans;
} int main(){
// freopen("int.txt", "r", stdin);
while(scanf("%d %d", &n, &T)){
if(!n && !T) break; for(int i = 0; i <= n; ++i)
sons[i].clear();
int x;
for(int i = 0; i < n; ++i){
scanf("%d", &x);
sons[x].push_back(i+1);
} int ans = 0; memset(dp, 0, sizeof(dp));
for(int i = n; i >= 0; --i)
dp[i] += DP(i);
printf("%d\n", dp[0]); }
return 0;
}
05-08 08:13