首页 > 代码库 > POJ 2486 Apple Tree

POJ 2486 Apple Tree

2024-07-25 10:17:48   211人阅读

　　很好也很烦的一个树形DP，昨天搞了一晚上是在想不出，后来没办法去看题解了，完事发现非常令人感动的是，我一开始设的状态都错了，然后就一直错了下去，还好及时的回头是岸了。

　　不说废话了，正题：

　　题目大意：给一棵树，n个节点，每个节点有一个权值，要求从节点1出发最多走k步，求所经过的点的权值和的最大值，每个点经过一次后就变为0；

　　最近做了一些树DP 也小小的总结了点规律，树形dp一般是设dp[rt][j]即以rt为根的子树j状态。这个题可以设

　　dp[rt][j][0]表示以rt为根的子树走j步最后不回到rt的解

　　dp[rt][j][1]表示以rt为根的子树走j步最后回到rt的解

　　方程看代码

　　然后对于每个儿子节点进行一次背包，背包容量为步数，看了半天题解一直感觉方程根本就不对，后来看到了是背包，(个人对于背包的一个描述就是放与不放的问题)，想了一下恍然大悟

 

　　

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 #include <vector> 7 #include <cmath> 8 #include <map> 9 #define INF 0x3f3f3f3f10 typedef __int64 LL;11 const int maxn = 110;12 const int maxv = 210;13 using namespace std;14 int dp[maxn][maxv][2],a[maxn];15 vector<int>son[maxn];16 vector<int>f[maxn];17 bool vis[maxn];18 int n,m;19 void build_tree(int rt)20 {21     //个人比较中意的一种建树的方法22     //首先用辅助vector f记录总共有多少条边，然后再从根节点开始dfs23     //找出与rt相连的边让其成为rt的子节点，然后vis标记这条边已经属于子节点24     //不能再成为别的节点的子节点25     //最后son[rt]中的元素都是rt的子节点26     //这样做主要还是不太会用邻接表  渣渣为自己找借口。。27     int len = f[rt].size(),x;28     for(int i = 0;i<len;++i)if(!vis[x = f[rt][i]]){29         son[rt].push_back(x);30         vis[x] = 1;31         build_tree(x);32     }33 }34 void init()35 {36     memset(vis,0,sizeof(vis));37     memset(son,0,sizeof(son));38     memset(f,0,sizeof(f));39     for(int i = 1;i<=n;++i)scanf("%d",a+i);40     for(int i = 1;i<n;++i)41     {42         int s,t;43         scanf("%d%d",&s,&t);44         f[s].push_back(t);45         f[t].push_back(s);46     }47     for(int i = 1;i<=n;++i)48         for(int j = 0;j<=m;++j)49             dp[i][j][0] = dp[i][j][1] = a[i];50     vis[1] = 1;51     build_tree(1);52 }53 void dfs(int rt)54 {55     int len = son[rt].size();56     for(int i = 0;i<len;++i){57         int u = son[rt][i];58         dfs(u);59         for(int j = m;j>=0;--j){60             for(int k = 0;k<=j;++k){61                 //从rt走到u最后还回到rt 因为还要回到rt 所以rt->u 和u->rt这两步要排除62                 if(k-2>=0)dp[rt][j][1] = max(dp[rt][j][1],dp[rt][j-k][1]+dp[u][k-2][1]);63                 //从rt走到u最后不回来  也就是把k-1大小的物品放入背包中  (k-1 是因为rt->u排除)64                 if(k-1>=0)dp[rt][j][0] = max(dp[rt][j][0],dp[rt][j-k][1]+dp[u][k-1][0]);65                 //从rt走到u还回来 最后停在别的儿子节点上66                 if(k-2>=0)dp[rt][j][0] = max(dp[rt][j][0],dp[rt][j-k][0]+dp[u][k-2][1]);67             }68         }69     }70 }71 int main()72 {73 //    freopen("in.txt","r",stdin);74     while(cin>>n>>m)75     {76         init();77         dfs(1);78         cout<<max(dp[1][m][0],dp[1][m][0])<<endl;79     }80     return 0;81 }

 

POJ 2486 Apple Tree


联系
我们