POJ2486---Apple Tree
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 7598 | Accepted: 2548 |
Description
Input
Each test case contains three parts.
The first part is two numbers N K, whose meanings we have talked about just now. We denote the nodes by 1 2 ... N. Since it is a tree, each node can reach any other in only one route. (1<=N<=100, 0<=K<=200)
The second part contains N integers (All integers are nonnegative and not bigger than 1000). The ith number is the amount of apples in Node i.
The third part contains N-1 line. There are two numbers A,B in each line, meaning that Node A and Node B are adjacent.
Input will be ended by the end of file.
Note: Wshxzt starts at Node 1.
Output
Sample Input
2 1 0 11 1 2 3 2 0 1 2 1 2 1 3
Sample Output
11 2
Source
树形dp
设dp[i][j][0] 表示 在以i为根的子树下走了j步最后不回到i,能够得到的最多苹果数
dp[i][j][1] 表示 在以i为根的子树下走了j步最后回到i,能够得到的最多苹果数
设u为某子树根,v为其中一个儿子节点
dp[u][i][1] = max(dp[u][i][1], dp[v][j - 2][1] + dp[u][i - j][1] + apple[v]);
dp[u][i][0] = max(dp[u][i][0], dp[u][i - j][1] + dp[v][j - 1][0] + apple[v]);
dp[u][i][0] = max(dp[u][i][0], dp[u][i - j][0] + dp[v][j - 2][1] + apple[v]);
/************************************************************************* > File Name: POJ2486.cpp > Author: ALex > Mail: [email protected] > Created Time: 2015年01月02日 星期五 11时30分01秒 ************************************************************************/ #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; vector <int> edge[110]; int dp[110][220][2]; int apple[110]; int n, m; void dfs(int u, int fa) { int size = edge[u].size(); for (int i = 0; i < size; ++i) { int v = edge[u][i]; if (v == fa) { continue; } dfs(v, u); for (int j = m; j >= 1; --j) { for (int k = 1; k <= j; ++k) { if (k >= 2) { dp[u][j][1] = max(dp[u][j][1], dp[u][j - k][1] + dp[v][k - 2][1] + apple[v]); dp[u][j][0] = max(dp[u][j][0], dp[v][k - 2][1] + dp[u][j - k][0] + apple[v]); } dp[u][j][0] = max(dp[u][j][0], dp[u][j - k][1] + dp[v][k - 1][0] + apple[v]); } } } } int main() { int u, v; while (~scanf("%d%d", &n, &m)) { memset (dp, 0, sizeof(dp)); for (int i = 1; i <= n; ++i) { edge[i].clear(); scanf("%d", &apple[i]); } for (int i = 1; i <= n - 1; ++i) { scanf("%d%d", &u, &v); edge[u].push_back(v); edge[v].push_back(u); } dfs(1, -1); printf("%d\n", dp[1][m][0] + apple[1]); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。