poj 2486 Apple Tree （樹形背包dp）

本文出自   http://blog.csdn.net/shuangde800

題目連結： poj-2486

題意

   給一個n個節點的樹，節點編号為1~n, 根節點為1, 每個節點有一個權值。

   從根節點出發，走不超過k步，問最多可以擷取多少權值？

思路

   因為和uva-1407 caves有點相似,是以沒想很久就AC了，但因為初始化問題WA了兩次

   f(i, j, 0): 表示子樹i，走j次，最終不用回到i點擷取的最大總權值

   f(i, j, 1): 表示子樹i，走j次，最終一定要回到i點擷取的最大總權值

   f(i, j, 1) = min{ min{ f(i, j-k, 1) + f(v, k-2, 1) | 2<=k<j }  | v是i的兒子節點}

   if(j==1)

       f(i, j, 0) = min{ min{f(i,j-k,1)+f(v,k,0) | 1<=k<=j } | v是i的兒子節點 }

   else

       f(i, j, 0) = min{ min{ min{f(i,j-k,1)+f(v,k-1,0), f(i,j-k,0)+f(v,k-2,1)} | 1<=k<=j } | v是i的兒子節點 }

   狀态轉移可能有點複雜， 還是看代碼更好了解。

代碼

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      ：poj-2486 Apple Tree
 *   @description : 樹形背包dp
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/08/23 22:17 All rights reserved. 
 *======================================================*/
 
#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
         #include 
        
          #include 
         
           #define MP make_pair using namespace std; typedef pair
          
           PII; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 110; vector
           
            adj[MAXN]; int val[MAXN]; bool vis[MAXN]; int f[MAXN][MAXN*2][2]; int n, k; int ans; void dfs(int u) { vis[u] = true; // init for (int i = 0; i <= k; ++i) f[u][i][0] = f[u][i][1] = val[u]; // dp for (int e = 0; e < adj[u].size(); ++e) { int v = adj[u][e]; if (vis[v]) continue; dfs(v); for (int i = k; i >= 1; --i) { for (int j = 1; j <= i; ++j) { if (j == 1) { int tmp1 = f[u][i-j][1] + f[v][j-1][0]; f[u][i][0] = max(f[u][i][0], tmp1); } else { int tmp1 = f[u][i-j][1] + f[v][j-1][0]; int tmp2 = f[u][i-j][0] + f[v][j-2][1]; f[u][i][0] = max(f[u][i][0], max(tmp1, tmp2)); f[u][i][1] = max(f[u][i][1], f[u][i-j][1] + f[v][j-2][1]); } } } } } int main(){ while (~scanf("%d %d", &n, &k)) { for (int i = 0; i <= n; ++i) adj[i].clear(); for (int i = 1; i <= n; ++i) scanf("%d", &val[i]); for (int i = 0; i < n - 1; ++i) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } memset(vis, 0, sizeof(vis)); memset(f, 0, sizeof(f)); dfs(1); printf("%d\n", f[1][k][0]); } return 0; }