UVA12186AnotherCrisis

xiaoxiao2021-02-28  104

//UVA12186AnotherCrisis #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN = 1e5 + 10; vector<int> son[MAXN]; int T; int dp(int u) {//计算激活一个申请在一种方式中所需要的workers的个数 if(son[u].empty()) return 1; int k = son[u].size(); vector<int> d; for(int i = 0; i < k; i++) d.push_back(dp(son[u][i])); sort(d.begin(), d.end());//为了取前c个累加 int c = (k * T - 1) / 100 + 1;//根据边界条件设定 int ans = 0; for(int i = 0; i < c; i++) ans += d[i]; return ans; } int main() { int N; //freopen("UVA12186out.txt", "w", stdout); while(scanf("%d%d", &N, &T) == 2 && N && T) { for(int i = 0; i <= N; i++) son[i].clear(); for(int i = 1; i <= N; i++) { int father; scanf("%d", &father); son[father].push_back(i); } printf("%d\n", dp(0)); } return 0; } /* 3 100 0 0 0 3 50 0 0 0 14 60 0 0 1 1 2 2 2 5 7 5 7 5 7 5 0 0 */
转载请注明原文地址: https://www.6miu.com/read-46325.html

最新回复(0)