,Author:magicpig@ZSU题目链接：?id=2486题目大意：有一棵n个结点的苹果树，每个结点上有一些苹果，现在从结点1开始走m步，问最多可以吃多少苹果，，一个结点的苹果被吃光后就没有了题目分析：弱渣做了好久啊，题意很好理解，关键是可能会回头，所以我们列状态的时候要考虑回头，不回头两种，即dp[u][i][0] 表示从结点u出发走了i步最后不回到0时吃掉的苹果数dp[u][i][1] 表示从结点u出发走了i步最后回到0时吃掉的苹果数分三种情况：u返回 v返回：u到别的子树后回到u再到v子树，遍历完v子树，回到v再回到u， u -> v， v -> u多出2步u返回 v不返回：u到别的子树后回到u再到v子树，然后一直向下遍历v子树 u -> v多出1步u不返回 v返回：u遍历完v子树再回到v再回到u再去遍历u的其他子树 u -> v， v -> u多出2步状态转移方程：dp[u][j + 2][1] = max(dp[u][j + 2][1], dp[u][k][1] + dp[v][j – k][1])dp[u][j + 1][0] = max(dp[u][j + 1][0], dp[u][k][1] + dp[v][j – k][0])dp[u][j + 2][0] = max(dp[u][j + 2][0], dp[u][k][0] + dp[v][j – k][1])vector：#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;int const MAX = 205;vector <int> t[MAX];int dp[MAX][MAX][2], val[MAX];int n, m;bool vis[MAX];void DFS(int u){vis[u] = true;for(int i = 0; i <= m; i++)dp[u][i][0] = dp[u][i][1] = val[u]; //从u出发至少可以获得val[u]个int len = t[u].size();for(int i = 0; i < len; i++){int v = t[u][i];if(!vis[v]){DFS(v);for(int j = m; j >= 0; j–){for(int k = 0; k <= j; k++){dp[u][j + 2][1] = max(dp[u][j + 2][1], dp[u][k][1] + dp[v][j – k][1]);dp[u][j + 1][0] = max(dp[u][j + 1][0], dp[u][k][1] + dp[v][j – k][0]);dp[u][j + 2][0] = max(dp[u][j + 2][0], dp[u][k][0] + dp[v][j – k][1]);}}}}}int main(){while(scanf("%d %d", &n, &m) != EOF){memset(dp, 0, sizeof(dp));memset(vis, false, sizeof(vis));for(int i = 1; i <= n; i++){scanf("%d", &val[i]);t[i].clear();}for(int i = 1; i < n; i++){int u, v;scanf("%d %d", &u, &v);t[u].push_back(v);t[v].push_back(u);}DFS(1);printf("%d\n", dp[1][m][0]);}}数组构树：#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int const MAX = 205;int dp[MAX][MAX][2], val[MAX];int head[MAX], cnt;int n, m;struct Edge{int to, next;}e[MAX * MAX / 2];void Add(int x, int y){e[cnt].to = y;e[cnt].next = head[x];head[x] = cnt++;}void DFS(int u, int fa){for(int i = 0; i <= m; i++)dp[u][i][0] = dp[u][i][1] = val[u];for(int i = head[u]; i != -1; i = e[i].next){int v = e[i].to;if(v != fa){DFS(v, u);for(int j = m; j >= 0; j–){for(int k = 0; k <= j; k++){dp[u][j + 2][1] = max(dp[u][j + 2][1], dp[u][k][1] + dp[v][j – k][1]);dp[u][j + 1][0] = max(dp[u][j + 1][0], dp[u][k][1] + dp[v][j – k][0]);dp[u][j + 2][0] = max(dp[u][j + 2][0], dp[u][k][0] + dp[v][j – k][1]);}}}}}int main(){while(scanf("%d %d", &n, &m) != EOF){cnt = 0;memset(dp, 0, sizeof(dp));memset(head, -1, sizeof(head));for(int i = 1; i <= n; i++)scanf("%d", &val[i]);for(int i = 1; i < n; i++){int u, v;scanf("%d %d", &u, &v);Add(u, v);Add(v, u);}DFS(1, -1);printf("%d\n", dp[1][m][0]);}}
人之所以有一张嘴，而有两只耳朵，原因是听的要比说的多一倍。
