POJ 2486 Apple Tree ——（树型DP）

　　题意是给出一棵树，每个点都有一个权值，从1开始，最多走k步，问能够经过的所有的点的权值和最大是多少（每个点的权值只能被累加一次）。

　　考虑到一个点可以经过多次，设dp状态为dp[i][j][k]，i表示当前从i出发，j表示最多走j步，k=0的话表示最后回到i点，否则不回到i点的子问题的答案。

　　转移见代码。

　　值得注意的是dfs中j循环的方向必须从大到小，因为如果从小到大，当前的j是从比其小的dp[u][j-t][...]更新过来的，而后者是根据走了v以后的更新过来的。换言之，如果从小到大，那么，走v贡献的权值就会被计算多次了，而题目中给的条件是，一个点的权值只能计算一次。拓展一下的话，如果一个点的权值可以被计算多次，那么应当从小到大循环j。

　　不妨以下面这组数据为例可以找到区别：

　　3 3
　　1 100 1
　　1 2
　　1 3

　　代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 using namespace std;

 const int N =  + ;

 int n,k;

 int val[N];

 vector<int> G[N];

 int dp[N][N*][]; // 0 表示回到原地

 void update(int & a,int b) {if(a < b) a = b;}

 int dfs(int u,int fa)

 {

     for(int i=;i<G[u].size();i++)

     {

         int v = G[u][i];

         if(v == fa) continue;

         dfs(v,u);

         // j必须从大到小(?)

         for(int j=k;j>=;j--)

         {

             for(int t=;t<=j;t++)

             {

                 // 最终都回到原地，那么左右都需要回到原地，此时需要多走两步 u->v & v->u

                 if(t >= ) update(dp[u][j][], dp[u][j-t][] + dp[v][t-][]);

                 // 最终不用回到原地，有只要左边或者右边一种选择不用回到原地即可

                 if(t >= ) update(dp[u][j][], dp[u][j-t][] + dp[v][t-][]);

                 update(dp[u][j][], dp[u][j-t][] + dp[v][t-][]);

             }

         }

     }

 }

 int main()

 {

     while(scanf("%d%d",&n,&k) == )

     {

         memset(dp,,sizeof dp);

         for(int i=;i<=n;i++)

         {

             G[i].clear();

             scanf("%d",val+i);

             for(int j=;j<=k;j++) dp[i][j][] = dp[i][j][] = val[i];

         }

         for(int i=;i<n;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             G[u].push_back(v);

             G[v].push_back(u);

         }

         dfs(, -);

         printf("%d\n",max(dp[][k][], dp[][k][]));

     }

     return ;

 }

巴特西

POJ 2486 Apple Tree ——（树型DP）

最新文章

热门文章