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;
}