首页 > 代码库 > UVA12186 Another Crisis
UVA12186 Another Crisis
题解:
树形DP
直属下属不小于T%的人签字。设父节点的子节点为k.所以是T*K/100,但是避免一些特殊情况。写成(T*K-1)/100+1(因为T>0，所以可以这样写)
dp(u)表示u给上级发信息最少需要多少子节点签字.
然后从最下面开始一层一层向上更新。但是dp在写时是从上到下写的，有个迭代过程
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 1e9typedef pair<int,int> P;const double eps=1e-9;const int maxnnode=11000;const int maxn=1e5+10;const ll mod=1000000007;int n,t;int d[maxn];vector<int> son[maxn];int dp(int u){ if(son[u].empty()) return 1; int k=son[u].size(); vector<int> d; for(int i=0;i<k;i++) d.pb(dp(son[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)&&n&&t){ for(int i=0;i<=n;i++) son[i].clear(); int a; for(int i=1;i<=n;i++){ scanf("%d",&a); son[a].pb(i); } printf("%d\n",dp(0)); } return 0;}
UVA12186 Another Crisis
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。