动态规划解决环保能量球最大收益问题

1. 题目背景与需求分析

这道来自GESP C++二级考试[2025年12月]的编程题，以"环保能量球"为背景设计了一个典型的数组处理问题。题目描述大致是这样的：

某环保机构开发了一种能量球收集系统，能量球按一定顺序排列，每个能量球有不同的能量值。系统每次可以选择收集当前序列中的某个能量球，并获得其能量值，但同时会导致相邻能量球的能量值减半。要求编程计算在给定能量球序列的情况下，能够获得的最大总能量值。

这类问题在实际编程竞赛和算法学习中非常典型，它考察了几个核心能力：

• 数组元素的遍历与处理
• 动态规划思想的初步应用
• 边界条件的处理能力
• 基本数学运算的实现

2. 解题思路与算法选择

2.1 暴力搜索的可能性

最直观的想法是尝试所有可能的收集顺序，计算每种情况下的总能量值，然后取最大值。对于n个能量球，这种方法的复杂度是O(n!)，当n较大时（比如n>20），计算量会变得不可接受。

提示：在编程竞赛中，通常n的限制条件会暗示解题方向。如果n≤20，可能暗示可以使用暴力搜索；而n≥1000则几乎肯定需要更高效的算法。

2.2 动态规划解法

更优的解法是使用动态规划。我们可以定义dp[i]表示前i个能量球能获得的最大能量值。对于每个位置i，我们有两种选择：

1. 收集第i个能量球：那么总能量为dp[i-2] + energy[i]（因为不能收集相邻的i-1）
2. 不收集第i个能量球：总能量保持为dp[i-1]

因此状态转移方程为：
dp[i] = max(dp[i-1], dp[i-2] + energy[i])

2.3 边界条件处理

需要特别注意初始条件：

• dp[0] = 0（没有能量球）
• dp[1] = energy[0]（只有一个能量球时只能选择它）

3. 完整代码实现与解析

cpp复制#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxEnergy(vector<int>& energy) {
    if (energy.empty()) return 0;
    if (energy.size() == 1) return energ