首页 > 程序开发 > 综合编程 > 其他综合 >

UVA12186 树形DP

2017-02-17

UVA12186 树形DP:一个公司有1个老板和n个员工,n个员工中有普通员工和中级员工。现在进行一次投票,若中级员工管理的普通员工中有T%的人投票,则中级员工也投票并递交给上级员工。

UVA12186 树形DP:一个公司有1个老板和n个员工,n个员工中有普通员工和中级员工。现在进行一次投票,若中级员工管理的普通员工中有T%的人投票,则中级员工也投票并递交给上级员工。求最少需要多少个普通员工投票,投票才能到达老板处。

题解

基础的树形DP,设d[u]为员工u想要投票给上级员工,最少需要多少个下级员工投票。若d[u]有k个下级员工,则至少需要(k*t-1)/100+1个下级员工投票才行。将所有下级员工d值排序,求前(k*t-1)/100+1个d值之和即为该员工d值。最后求出d[0],即为本题答案。

注意事项

vector排序方法为sort(vector.begin(),vector.end())

代码

#include 
#include
#include
#include
#include

using namespace std;
vector son[100010];
int t;

int dp(int u){
    if(son[u].empty()){
        return 1;
    }
    vector d;
    int k=son[u].size();
    for(int i=0;i
        
   
相关文章
最新文章
热点推荐