#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=100000+5;
int T;
//d(u) 第u个人至少需要多少工人
vector<int> sons[maxn];
int dp(int u)
{int k=sons[u].size();if(!k) return 1; // 工人 vector<int> d;for(int i=0;i<k;i++)d.push_back(dp(sons[u][i])); //每一个直系下属递交的需要多少工人数sort(d.begin(),d.end()); int c=ceil(k*T/100.0); //直系下属至少多少人递交 int ans=0; for(int i=0;i<c;i++) ans+=d[i]; //取需要工人最少的前c个直系下属的申请书 return ans;
}
int main()
{int N;while(scanf("%d%d",&N,&T)==2&&N&&T){for(int i=0;i<=N;i++) sons[i].clear();for(int i=1;i<=N;i++){ int f; cin>>f;sons[f].push_back(i); //i的上司是f }cout<<dp(0)<<endl;}return 0;
}
详细解决方案
UVA 12186 Another Crisis
热度:12 发布时间:2023-09-23 09:12:11.0
相关解决方案
- 紫书 例题 9-12 UVa 12186 (树形dp)
- UVA 12186 Another Crisis
- UVa - 12186 - Another Crisis ( 树形DP )
- HOJ 2110 Crisis of HDU(普通母函数,模板题)
- 麻烦的DP-BZOJ-1605-[Usaco2008 Open]Crisis on the Farm 牧场危机
- HDU 3749 Financial Crisis 点双连通分量
- HDU3749 Financial Crisis(点双连通分量+并查集)
- 例题9-12 UVa12186 Another Crisis(树型DP)
- UVA12186 工人的请愿书 Another Crisis 题解
- 【题解】UVA151 【Power Crisis】