思路:dp[i]表示让上司i签字至少需要多少工人签字。
转移方程:将i的所有节点根据所需工人数量升序排序,设i需要k个下属签字,dp[i] = sum{dp[v]| 0 <= v <k}
AC代码:
#include<cstdio> #include<algorithm> #include<cstring> #include<utility> #include<string> #include<iostream> #include<map> #include<set> #include<vector> #include<queue> #include<stack> using namespace std; #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> const int maxn = 1e5 + 5; vector<int>son[maxn]; int t; int dfs(int u) { int n = son[u].size(); if(!n) return 1; //工人 vector<int>cnt; for(int i = 0; i < n; ++i) { int v = son[u][i]; cnt.push_back(dfs(v)); } sort(cnt.begin(), cnt.end()); int c = (n*t - 1) / 100 + 1; int ans = 0; for(int i = 0; i < c; ++i) ans += cnt[i]; return ans; } int main() { int n; while(scanf("%d%d", &n, &t) == 2 && n) { for(int i = 0; i <= n; ++i) son[i].clear(); int pre; for(int i = 1; i <= n; ++i) { scanf("%d", &pre); son[pre].push_back(i); } printf("%d\n", dfs(0)); } return 0; }
如有不当之处欢迎指出!