HDU 4169 Wealthy Family - c++编程基础

题意：

n个节点的树每个节点上有个价值要求选出k个两两互相没有祖孙关系的节点使得价值和最大

思路：

明显的树形dp 如果用dp[fa][i]表示fa子树取i个点的最大价值和则有转移 dp[fa][i]=max(dp[son][k]+dp[fa][i-k])

但是如果这样开数组会MLE 所以本题猥琐的使用dfs内部开数组的方式这样借助全局变量的帮助我们可以避免MLE

（其实如果树是一条链照样MLE 这个方法很不科学但是数据水能AC）

如果是现场赛反正电脑闲着也是闲着一定要写这个不要脸的算法！！

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; #define N 310 #define M 150010 int n, m; int sz, save[N], tmp[N], val[M]; int tot, head[M]; struct edge { int v, next; } ed[M]; void add(int u, int v) { ed[tot].v = v; ed[tot].next = head[u]; head[u] = tot++; } void dfs(int u) { int dp[N]; memset(dp, 0, sizeof(dp)); int cnt = 0; for (int i = head[u]; ~i; i = ed[i].next) { int v = ed[i].v; dfs(v); memset(tmp, 0, sizeof(tmp)); for (int j = 0; j <= cnt; j++) { for (int k = 0; k <= sz && j + k <= m; k++) { tmp[j + k] = max(tmp[j + k], dp[j] + save[k]); } } cnt = min(m, cnt + sz); memcpy(dp, tmp, sizeof(int) * (cnt + 1)); } dp[1] = max(dp[1], val[u]); if (!cnt) cnt = 1; sz = cnt; memcpy(save, dp, sizeof(int) * (cnt + 1)); } int main() { while (~scanf("%d%d", &n, &m)) { tot = 0; memset(head, -1, sizeof(int) * (n + 1)); for (int i = 1; i <= n; i++) { int fa; scanf("%d%d", &fa, &val[i]); add(fa, i); } memset(save, 0, sizeof(save)); dfs(ed[head[0]].v); if (save[m]) printf("%d\n", save[m]); else printf("impossible\n"); } return 0; }