首页 > 代码库 > POJ 2486

POJ 2486

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

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

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

 

实现代码1:

 1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 using namespace std; 5  6 const int MAX=105; 7 vector<int>G[MAX]; 8 int num[MAX],dp_back[MAX][MAX*2],dp_to[MAX][MAX*2]; 9 int tback[MAX*2],tto[MAX*2];10 int n,s;11 12 void init(){13     for(int i=1;i<=n;i++)14     G[i].clear();15     memset(dp_back,0,sizeof(dp_back));16     memset(dp_to,0,sizeof(dp_to));17 }18 19 void dfs(int u,int f){20     int size=G[u].size();21     for(int i=0;i<size;i++){22         int v=G[u][i];23         if(v!=f){24             dfs(v,u);25             for(int p=1;p<=s;p++){26                 tback[p]=dp_back[u][p];27                 tto[p]=dp_to[u][p];28                 for(int k=0;k<=p;k++){29                     if(p-k-2>=0){30                         tback[p]=max(tback[p],dp_back[u][p-k-2]+dp_back[v][k]+num[v]);31                     }32                     if(p-k-1>=0){33                         tto[p]=max(tto[p],dp_back[u][p-k-1]+dp_to[v][k]+num[v]);34                     }35                     if(p-k-2>=0){36                         tto[p]=max(tto[p],dp_to[u][p-k-2]+dp_back[v][k]+num[v]);37                     }38                 }39             }40             for(int j=0;j<=s;j++){41                 dp_back[u][j]=tback[j];42                 dp_to[u][j]=tto[j];43             }44         }45     }46 }47 48 int main(){49     int u,v;50     while(scanf("%d%d",&n,&s)!=EOF){51         init();52         for(int i=1;i<=n;i++)53         scanf("%d",&num[i]);54         for(int i=1;i<n;i++){55             scanf("%d%d",&u,&v);56             G[u].push_back(v);57             G[v].push_back(u);58         }59         dfs(1,0);60         int ans=max(dp_to[1][s],dp_back[1][s]);61         ans+=num[1];62         printf("%d\n",ans);63     }64     return 0;65 }
View Code

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

 

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

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

 1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 using namespace std; 5  6 const int MAX=105; 7 vector<int>G[MAX]; 8 int num[MAX],dp_back[MAX][MAX*2],dp_to[MAX][MAX*2]; 9 int tback[MAX*2],tto[MAX*2];10 int n,s;11 12 void init(){13     for(int i=1;i<=n;i++)14     G[i].clear();15     memset(dp_back,0,sizeof(dp_back));16     memset(dp_to,0,sizeof(dp_to));17 }18 19 void dfs(int u,int f){20     int size=G[u].size();21     dp_back[u][0]=num[u];22     dp_to[u][0]=num[u];23     for(int i=0;i<size;i++){24         int v=G[u][i];25         if(v!=f){26             dfs(v,u);27             for(int p=0;p<=s;p++){28                 tback[p]=dp_back[u][p];29                 tto[p]=dp_to[u][p];30                 for(int k=0;k<=p;k++){31                     if(p-k-2>=0){32                         tback[p]=max(tback[p],dp_back[u][p-k-2]+dp_back[v][k]);33                     }34                     if(p-k-1>=0){35                         tto[p]=max(tto[p],dp_back[u][p-k-1]+dp_to[v][k]);36                     }37                     if(p-k-2>=0){38                         tto[p]=max(tto[p],dp_to[u][p-k-2]+dp_back[v][k]);39                     }40                 }41             }42             for(int j=0;j<=s;j++){43                 dp_back[u][j]=tback[j];44                 dp_to[u][j]=tto[j];45             }46         }47     }48 }49 50 int main(){51     int u,v;52     while(scanf("%d%d",&n,&s)!=EOF){53         init();54         for(int i=1;i<=n;i++)55         scanf("%d",&num[i]);56         for(int i=1;i<n;i++){57             scanf("%d%d",&u,&v);58             G[u].push_back(v);59             G[v].push_back(u);60         }61         dfs(1,0);62     //    int ans=max(dp_to[1][s],dp_back[1][s]);63     //    ans+=num[1];64         int ans=0;65         for(int i=0;i<=s;i++)66         ans=max(ans,max(dp_back[1][i],dp_to[1][i]));67         printf("%d\n",ans);68     }69     return 0;70 }
View Code

 

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

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