欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVa12186 - Another Crisis(树形dp)

程序员文章站 2022-06-02 12:06:01
...

简介:
一个公司有1个老板和n个员工,n个员工中有普通员工和中级员工
现在进行一次投票,若中级员工管理的普通员工中有T%的人投票,则中级员工也投票并递交给上级员工
求最少需要多少个普通员工投票,投票才能到达老板处

分析:
基础的树形dp,供消遣
为了方便,用一个vector存储结点的儿子
设f[i]表示为了让信息传到i,需要的最少人数

唯一有一点不直白的就是我们需要计算到底至少需要多少人
设结点u的儿子有k个,则:

c=(k*T-1)/100+1
这个柿子确实很迷,但是不会出错(应该是考虑到了四舍五入)
(我试了一下直接计算并四舍五入,这样得到的数值就不对了)

接下来就有一点贪心了
把所有的儿子结点的f值排序,选最小的c个加起来就是当前点的f值
注:1级员工为2级员工的上司

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

vector<int> son[100005];
int n,T;

int doit(int now)
{
    if (son[now].size()==0) return 1;

    vector<int> d;
    for (int i=0;i<son[now].size();i++)
        d.push_back(doit(son[now][i]));//递归now级以下doit函数

    sort(d.begin(),d.end());
    int k=son[now].size();
    int c=(k*T-1)/100+1,ans=0;
    for (int i=0;i<c;i++) 
        ans+=d[i];

    return ans;
}

int main()
{
    while (scanf("%d%d",&n,&T)!=EOF&&n)
    {
        for (int i=0;i<=n;i++) son[i].clear();
        for (int i=1;i<=n;i++)
        {
            int fa;
            scanf("%d",&fa);
            son[fa].push_back(i);
        }
        printf("%d\n",doit(0));
    }
    return 0;
}

UVa12186 - Another Crisis(树形dp)