本文共 2672 字，大约阅读时间需要 8 分钟。

看着很玄幻，其实也就是dfs+dp。

然后满足那么一个关系，在一个树上，有上级下级树形关系

uva12186是紫书上的题目。

需要注意题目：每层只要它的直接下属来就好了，不用考虑到所有底层员工，按照书上给的式子，c=(k*T-1)/100+1

每次这样来就可以了

之后贪心选取花费最少的。

写的时候遇到一点小问题：

if(d[dd]==0) d[dd]=dfs(dd);

v.push_back(d[dd]);

(我喜欢这么写清楚一点.... )这里要注意d[dd]要赋值，不然dfs跑一遍，返回一个ans要存储下来，不然浪费掉了

还有就是读入边的时候，不要读反了（最好画个图）

最后就是思路很重要，好好想想怎么实现，感觉还是挺神奇的

关于式子有点小问题，实验了一下，写成下面这种也可以，取整罢了。。。。

我最开始还被吓死了。。。答案是一样的，就是注意转换成double再ceil

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int n; int p;int a[100005];int d[100005];vector
        
          g[100005];int dfs(int x) { // this time ,how will we start our journey //let's first find what we need // we got 0 at first , we want to see the sons of 0 // and if it reaches the end(g[i]==0) //returns an ans if (g[x].size() == 0)return 1; // do you know that ! he is 1 int sum = 0; vector
         
           v; for (int i = 0; i
          
           > n >> p) { if (n == 0 || p == 0)return 0; memset(d, 0, sizeof(d)); for (int i = 0; i <= n; i++)g[i].clear(); int u, v; for (int i = 1; i <= n; i++) { cin >> u;//just get father // u is father //BUT!!! DO REMEMBER WHO IS U IN THE TITLE //BUT!!! DO REMEMBER WHO IS U IN THE TITLE g[u].push_back(i); // cout << u << "-------" << g[u].size() << endl; } cout << dfs(0) << endl; } return 0;}
          
         
        
       
      
     
    
   

HDU 1512 

另外，这个代码习惯不好。。。 不用if（xxx==0）bfs（xxx）直接后面的就好了

因为bfs里面是五环的（没有环 树上）

如果是无根的 双向边 可以加个-1访问标记（加个1的 bool比int快和省空间。。。。 ）

还有注释写了一堆写的我好烦（不）一堆的写在外面  注释 在干嘛的写在里面

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int a[6005]; //happy- numbersint n;int fa[6005];// finds final fatherint dp[6005][2];vector
        
         g[6005];void dfs(int x) { //dp[x][1] = a[x]; // 记得这里初始化!!!!! //if he goes we can get happy number like so //but he has many employee //so he needs to do many times int sum0 = 0; int sum1 = 0; for (int i = 0; i
         
          > n) { memset(dp, 0, sizeof dp); memset(fa, -1, sizeof(fa)); for (int i = 1; i <= n; i++)cin >> dp[i][1],g[i].clear();//happy numbers int u, v; while (cin >> u >> v) { // u is father if (u == 0 && v == 0)break; g[v].push_back(u); fa[u] = v; } //after that finds father first // go back for others int rec = 1; while (fa[rec] != -1)//if have changed continues searching { rec = fa[rec]; } //fa[1] //***这里final fa其实是5 //rec is the final father dfs(rec);//get all resulus cout << max(dp[rec][0], dp[rec][1]) << endl; } return 0;}
         
        
       
      
     
    
   

HDU这个题.....  laji/....

Hdu是多组数据,,..  即使没说，用了while和memset就a了

终于明白这个是在讲什么了.. 没有数据的生活真的好苦(手再)

zj说 这需要经验 经验 经验

同样的标题 复制进去 找URAL交  accept

........但是人家数据不公开啊

hdu啊hdu(滑稽)