UVA 12186 Another Crisis——dp

UVA 12186 Another Crisis——dp

水题

#include #include #include #include #include #include using namespace std;const int maxn = 1e5 + 10;vector G[maxn];int n, T, dp[maxn];int dfs(int u) { if (G[u].size() == 0) return dp[u] = 1; vector ans; int k = G[u].size(); for (int i = 0; i < k; i++) { int v = G[u][i]; dfs(v); ans.push_back(dp[v]); } k = (int)ceil(1.0*k*T/100); sort(ans.begin(), ans.end()); for (int i = 0; i < k; i++) { dp[u] += ans[i]; } return dp[u];}int main() { while (~scanf("%d %d", &n, &T) && (n+T)) { for (int i = 0; i <= n; i++) G[i].clear(); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); G[x].push_back(i); } memset(dp, 0, sizeof(dp)); printf("%d\n", dfs(0)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。