本文共 2155 字，大约阅读时间需要 7 分钟。

从1号点出发，每次经过一个点，可以获取该点上的苹果。目标是通过最多m步，找到能够获取的苹果最大数量。这个问题可以通过动态规划来解决，其中dp[u][j]表示从u号点出发走j步后回到u点能得到的苹果最大数量，而ans[u][j]则表示从u号点出发走j步不一定回到u点能得到的苹果最大数量。

递归关系分析

代码分析

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct Edge {    int y, next;};void add_edge(int x, int y) {    e[k].y = y;    e[k].next = first[x];    first[x] = k++;}void dfs(int u, int fa, int m) {    ans[u][0] = dp[u][0] = val[u];    for (int i = first[u]; i != -1; i = e[i].next) {        int v = e[i].y;        if (v == fa) continue;        dfs(v, u, m);        for (int j = m; j >= 0; j--) {            for (int k = j; k >= 0; k--) {                dp[u][j + 2] = max(dp[u][j + 2], dp[v][k] + dp[u][j - k]);                ans[u][j + 2] = max(dp[v][k] + ans[u][j - k], ans[u][j + 2]);                ans[u][j + 1] = max(ans[v][k] + dp[u][j - k], ans[u][j + 1]);            }        }    }}int main() {    // 读取输入    int n, m;    while (scanf("%d%d", &n, &m) == 2) {        for (int i = 1; i <= n; i++) {            scanf("%d", val + i);        }        memset(first, -1, sizeof(first));        k = 0;        for (int i = 1; i <= n; i++) {            scanf("%d", val + i);            // 添加边            while (true) {                scanf("%d", &y);                if (y == -1) break;                add_edge(i, y);            }        }        // 调用dfs        dfs(1, -1, m);        // 输出结果        for (int i = 1; i <= n; i++) {            for (int j = 0; j <= m; j++) {                if (j == 0) {                    cout << val[i] << " ";                } else {                    cout << ans[i][j] << " ";                }            }            cout << endl;        }    }}
     
    
   

优化总结

该代码通过深度优先搜索（DFS）遍历树结构，利用动态规划数组dp和ans来记录从各节点出发的最大苹果数量。递归关系确保了所有可能的路径都被考虑，包括直接返回和经过其他子节点的情况。代码注重正确初始化和更新递归关系，确保了最优解的正确性。

转载地址：http://lyxfk.baihongyu.com/