POJ_2486 Apple Tree

POJ 2486 Apple Tree

http://poj.org/problem?id=2486

题意：

给你一颗苹果树，有N个节点每个节点上都有一定数目的苹果也就是有一个权值，当你经过这个节点时你将得到这个权值，重复走节点是只能算一次。
给你N-1条边，问你只能走K步能得到的最大权值和。

数据：

(1<=N<=100, 0<=K<=200)

思路：

 1. 树形DP。
2. 由于可以返回根节点，所以需要多一维来表示是否返回过根。
3. DP的形式：
dp[i][j][0]表示最终不回到i可以得到的最大苹果数量。
dp[i][j][1]表示以i为根节点步行j步，且最终回到i，可以得到的最大苹果数量。
即是0表示不回到该节点，1表示最后回到该节点。
4. 转移方程：
dp[x][j][0]=max(dp[x][j][0],dp[x][j-k][1]+dp[e][k-1][0]);
dp[x][j][0]=max(dp[x][j][0],dp[x][j-k][0]+dp[e][k-2][1]);
dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][1]+dp[e][k-2][1]);
注：其中k-1表示根到儿子这条边只走了一次，k-2则表示有返回的（即是两次）。
而j-k则表示从另一棵子树的步数。

代码：

#include <iostream>
#include <string.h>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
const int N = 600;
const int M = 1000000007 ;
// const LL INF = 1<<32;
int n,m,cc;
int s[N],a,b;
int vis[N];
vector <int> g[N];
int dp[N][N][3];
void add(int a,int b)
{
g[a].push_back(b);
g[b].push_back(a);
}
void ini()
{
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
memset(s,0,sizeof(s));
for (int i=0;i<=n;i++)
g[i].clear();
}
void dfs(int x)
{
vis[x]=1;
for (int i=0;i<g[x].size();i++)
{
int e=g[x][i];
if (vis[e])
continue;
dfs(e);
for (int j=m;j>=1;j--)
{
for (int k=1;k<=j;k++)
{
//0表示不回到该节点，1表示最后回到该节点
dp[x][j][0]=max(dp[x][j][0],dp[x][j-k][1]+dp[e][k-1][0]);
dp[x][j][0]=max(dp[x][j][0],dp[x][j-k][0]+dp[e][k-2][1]);
dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][1]+dp[e][k-2][1]);
}
}
}
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
ini();
for (int i=1;i<=n;i++)
{
scanf("%d",&s[i]);
for (int j=0;j<=m;j++)
dp[i][j][0]=dp[i][j][1]=s[i];
}
for (int i=0;i<n-1;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
}
dfs(1);
printf("%dn", max(dp[1][m][0],dp[1][m][1]));
}
return 0;
}
/*
1 1
0
4 2
1 2 3 4
1 2
2 3
3 4
8 4
0 1 4 3 3 2 4 1
1 2
1 3
1 4
2 5
2 6
3 7
3 8
8 4
2 1 4 3 3 2 4 1
1 2
1 3
1 4
2 5
2 6
3 7
3 8
*/
// ANS : 0 6 11 13

最后

以上就是满意玫瑰为你收集整理的POJ_2486 Apple Tree的全部内容，希望文章能够帮你解决POJ_2486 Apple Tree所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。