GESP 六级 · GESP 202509 C++ 六级 第 25 题

有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。

// bananas: 香蕉的甜度
void findSelectedBananas(vector<int>& bananas, vector<int>& dp) {
    vector<int> selected;
    int i = bananas.size() - 1;

    while (i >= 0) {
        if (i == 0) {
            selected.push_back(0);
            break;
        }

        if (dp[i] == dp[i-1]) {
            i--;
        } else {
            selected.push_back(i);
            i -= 2;
        }
    }

    reverse(selected.begin(), selected.end());
    cout << "小猴子吃了第: ";
    for (int idx : selected)
        cout << idx+1 << " ";
    cout << "个香蕉" << endl;
}

int main() {
    vector<int> bananas = {1, 2, 3, 1}; // 每个香蕉的甜
    vector<int> dp(bananas.size());
    dp[0] = bananas[0];
    dp[1] = max(bananas[0], bananas[1]);
    for (int i = 2; i < bananas.size(); i++) {
        dp[i] = max(bananas[i] + dp[i-2], dp[i-1]);
    }
    findSelectedBananas(bananas, dp);
    return 0;
}

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】动态规划|递推关系|回溯构造解

1. 🎯 考纲定位

本题属于 GESP 六级 C++ 算法模块第 3 单元"动态规划"的典型考题。命题人刻意选择"回溯构造最优解路径"这个高阶考察点——绝大多数考生能算出 dp 值却栽在如何还原具体方案上，因为 GESP 六级明确要求"不仅要算出最优值，还要输出方案"，这直接筛掉了只会套公式的选手。