UVa 12186 Another Crisis （DP）

题意：有一个老板和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;

}