首页 > 代码库 > dp uva12186树上的动态规划
dp uva12186树上的动态规划
http://vjudge.net/problem/UVA-12186
d(u)表示让u给上级发信最少需要多少工人
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int N,T,f; vector<int> sons[maxn]; int dp(int u){ if(sons[u].empty()) return 1; int k = sons[u].size(); vector<int> d; for(int i=0; i<k; i++) d.push_back(dp(sons[u][i])); sort(d.begin(),d.end()); int c = (k*T-1)/100 + 1; int ans = 0; for(int i=0; i<c; i++) ans += d[i]; return ans; } int main(){ 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++){ scanf("%d",&f); sons[f].push_back(i); } printf("%d\n",dp(0)); } }
dp uva12186树上的动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。