（UVA - 12186）Another Crisis（树状dp）
https://vjudge.net/problem/UVA-12186#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define pb push_back
#define rep(i,a,n) for(int i=a; i<n; i++)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int n,T;
vector<int>son;
int tree_dp(int u)
{
if(son.empty()) return 1;
int k=son.size();
vector<int>d;
rep(i,0,k) d.pb(tree_dp(son));
sort(d.begin(),d.end());
int c=(k*T-1)*0.01+1,ans=0;///c为最少的工人数
rep(i,0,c) ans+=d;
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&T)&&n&&T)
{
int x;
rep(i,0,n+1) son.clear();
rep(i,1,n+1) scanf("%d",&x),son.pb(i);///son记录其直接下属
printf("%d\n",tree_dp(0));
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_13696685/2990622
页:
[1]