POJ 2486

因为苹果可能在不同的子树中，所以，很容易想到设状态dp_back[i][j]为以i点为树根走j步并回到i点的最大苹果数与dp_to[i][j]不回到i点的两个状态。

于是，转移方程就很明显了。只是注意要减去一来一回，或者不回的边。树形DP里套背包。

但这题远比这复杂，个人认为。因为在实现上细节太多。

实现代码1：

 #include <iostream>

 #include <cstdio>

 #include <vector>

 using namespace std;

 const int MAX=;

 vector<int>G[MAX];

 int num[MAX],dp_back[MAX][MAX*],dp_to[MAX][MAX*];

 int tback[MAX*],tto[MAX*];

 int n,s;

 void init(){

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

     G[i].clear();

     memset(dp_back,,sizeof(dp_back));

     memset(dp_to,,sizeof(dp_to));

 }

 void dfs(int u,int f){

     int size=G[u].size();

     for(int i=;i<size;i++){

         int v=G[u][i];

         if(v!=f){

             dfs(v,u);

             for(int p=;p<=s;p++){

                 tback[p]=dp_back[u][p];

                 tto[p]=dp_to[u][p];

                 for(int k=;k<=p;k++){

                     if(p-k->=){

                         tback[p]=max(tback[p],dp_back[u][p-k-]+dp_back[v][k]+num[v]);

                     }

                     if(p-k->=){

                         tto[p]=max(tto[p],dp_back[u][p-k-]+dp_to[v][k]+num[v]);

                     }

                     if(p-k->=){

                         tto[p]=max(tto[p],dp_to[u][p-k-]+dp_back[v][k]+num[v]);

                     }

                 }

             }

             for(int j=;j<=s;j++){

                 dp_back[u][j]=tback[j];

                 dp_to[u][j]=tto[j];

             }

         }

     }

 }

 int main(){

     int u,v;

     while(scanf("%d%d",&n,&s)!=EOF){

         init();

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

         scanf("%d",&num[i]);

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

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

             G[u].push_back(v);

             G[v].push_back(u);

         }

         dfs(,);

         int ans=max(dp_to[][s],dp_back[][s]);

         ans+=num[];

         printf("%d\n",ans);

     }

     return ;

 }

这是我WA了N久后看了别人的改过来的，每次在DP时才把根节点的值加上。说不清为什么，但是对了。

另一个是我原本WA的代码，可以把OJ的讨论板所有数据都过了，但依然WA，后来研究了好久，发现自己代码上的一个问题，那就是当最大步数超过边数的两倍时，就会出现问

题，于是，我只好投机一点，最后扫描一次结果值来获得正确值了。

 #include <iostream>

 #include <cstdio>

 #include <vector>

 using namespace std;

 const int MAX=;

 vector<int>G[MAX];

 int num[MAX],dp_back[MAX][MAX*],dp_to[MAX][MAX*];

 int tback[MAX*],tto[MAX*];

 int n,s;

 void init(){

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

     G[i].clear();

     memset(dp_back,,sizeof(dp_back));

     memset(dp_to,,sizeof(dp_to));

 }

 void dfs(int u,int f){

     int size=G[u].size();

     dp_back[u][]=num[u];

     dp_to[u][]=num[u];

     for(int i=;i<size;i++){

         int v=G[u][i];

         if(v!=f){

             dfs(v,u);

             for(int p=;p<=s;p++){

                 tback[p]=dp_back[u][p];

                 tto[p]=dp_to[u][p];

                 for(int k=;k<=p;k++){

                     if(p-k->=){

                         tback[p]=max(tback[p],dp_back[u][p-k-]+dp_back[v][k]);

                     }

                     if(p-k->=){

                         tto[p]=max(tto[p],dp_back[u][p-k-]+dp_to[v][k]);

                     }

                     if(p-k->=){

                         tto[p]=max(tto[p],dp_to[u][p-k-]+dp_back[v][k]);

                     }

                 }

             }

             for(int j=;j<=s;j++){

                 dp_back[u][j]=tback[j];

                 dp_to[u][j]=tto[j];

             }

         }

     }

 }

 int main(){

     int u,v;

     while(scanf("%d%d",&n,&s)!=EOF){

         init();

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

         scanf("%d",&num[i]);

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

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

             G[u].push_back(v);

             G[v].push_back(u);

         }

         dfs(,);

     //    int ans=max(dp_to[1][s],dp_back[1][s]);

     //    ans+=num[1];

         int ans=;

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

         ans=max(ans,max(dp_back[][i],dp_to[][i]));

         printf("%d\n",ans);

     }

     return ;

 }

两个代码除了初始化的位置不一样，其他都是一样的。但我感觉代码2更符合本来的转移方程，你看一下初始化的位置就明白。但最终问题时，不能处理好，那就是当最大步数超过边数的两倍时问题，因为我在初始化时就认为这是一种不可能的情况了。。。

所以，请路过大牛给指点，以去掉最后的扫描一次得到结果。。。

巴特西

POJ 2486

最新文章

热门文章