题目大意:一家工厂,一个老板(编号为0),n个工人(编号1~n),其中,有的工人是中层领导,管辖一部分其他工人。现在大家要签署一份加薪申请书,但是按照规定不能越级上访,所以只能通过一层层的中间领导传到老板手中。当某个中间领导的手下签名员工人数达到 m% 时,他也会签上自己的名字。为确保申请书顺利到达老板手中,至少需要多少名员工签名。
题目分析:定义d(i)表示员工 i 将申请书传给上一级所需的最少签名人数。设k为i的“儿子”数目,则最少需要的签名人数为 c=(k*m-1)/100+1。所以dp(i)=sum(dp(j))。(其中,j是i的儿子,并且dp(j)是前c个最小的。
代码如下:
# include<iostream>
# include<cstdio>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std;
int n,m;
vector<int>sons[100005];
int DP(int u)
{
if(sons[u].empty())
return 1;
vector<int>d;
int k=sons[u].size();
for(int i=0;i<k;++i)
d.push_back(DP(sons[u][i]));
sort(d.begin(),d.end());
int c=(k*m-1)/100+1;
int ans=0;
for(int i=0;i<c;++i)
ans+=d[i];
return ans;
}
int main()
{
int a;
while(scanf("%d%d",&n,&m)&&n+m)
{
for(int i=0;i<=n;++i)
sons[i].clear();
for(int i=1;i<=n;++i){
scanf("%d",&a);
sons[a].push_back(i);
}
printf("%d\n",DP(0));
}
return 0;
}