金苹果岛与最大代码能力：动态规划算法详解

题目描述

你是一位代码勇者，来到了传说中的金苹果岛。岛上有两种苹果：

红苹果: 随处可见，食用后代码能力会提升一定值（可能为负）。* 金苹果: 稀有美味，食用后代码能力直接翻倍。

你的初始代码能力为 1。苹果仙子会赠送你 n 个红苹果和 m 个金苹果，你需要吃光所有苹果。红苹果的食用顺序由仙子规定，但你可以自由选择何时吃金苹果。

你的目标是：找到一种吃苹果的策略，使得最终离开金苹果岛时的代码能力最大化。

输入格式

第一行包含两个正整数 n 和 m，分别表示红苹果和金苹果的数量 (n ≤ 10^5, m ≤ 10)。

第二行包含 n 个整数 a_i (|a_i| ≤ 10)，表示每个红苹果对代码能力的提升值。

输出格式

输出一个整数，表示离开金苹果岛时可能获得的最大代码能力。

样例 #1

样例输入 #1

6 21 -2 3 1 -6 5

样例输出 #1

样例解释

一种最优策略是：

吃掉红苹果 1, -2, 3, 1，代码能力变为 4。2. 吃掉 2 个金苹果，代码能力变为 16。3. 吃掉红苹果 -6, 5，代码能力变为 15。

样例 #2

样例输入 #2

8 35 -3 -8 2 4 -11 9 1

样例输出 #2

提示

对于 10% 的数据，a_i ≥ 0。* 对于 30% 的数据，m = 0。* 对于 70% 的数据，m = 1。* 对于 100% 的数据，n ≤ 10^5, m ≤ 10, |a_i| ≤ 10。

C++ 代码实现cpp#include #include #include using namespace std;

int main() { int n, m; cin >> n >> m; vector apples(n); for (int i = 0; i < n; i++) { cin >> apples[i]; }

// dp[i][j] 表示吃完前 i 个红苹果，使用 j 个金苹果后的最大能力值    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));    dp[0][0] = 1; 

for (int i = 1; i <= n; ++i) {        for (int j = 0; j <= m; ++j) {            // 不使用金苹果            dp[i][j] = max(dp[i][j], dp[i - 1][j] + apples[i - 1]);             // 使用金苹果            if (j > 0) {                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] * 2);             }        }    }

long long maxAbility = 1;    for (int j = 0; j <= m; ++j) {        maxAbility = max(maxAbility, dp[n][j]);    }

cout << maxAbility << endl;    return 0;}

解题思路

本题可以使用动态规划算法求解。

状态定义: 定义 dp[i][j] 表示吃完前 i 个红苹果，使用 j 个金苹果后的最大能力值。2. 状态转移方程: 对于每个状态 dp[i][j]，有两种选择： * 不吃金苹果: dp[i][j] = max(dp[i][j], dp[i - 1][j] + apples[i - 1])，即当前能力值等于吃完前 i-1 个苹果后的最大能力值加上当前红苹果的能力值。 * 吃金苹果: dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] * 2)，即当前能力值等于吃完前 i-1 个苹果，使用 j-1 个金苹果后的最大能力值的两倍。3. 初始状态: dp[0][0] = 1，表示初始代码能力为 1。4. 最终结果: 遍历 dp[n][j] (0 ≤ j ≤ m)，找到最大值即为最终答案。

复杂度分析

时间复杂度: O(nm)，其中 n 是红苹果数量，m 是金苹果数量。* 空间复杂度: O(nm)，存储动态规划状态空间。

总结

本题通过动态规划算法，有效解决了金苹果岛上的代码能力最大化问题。通过合理定义状态和状态转移方程，我们找到了吃苹果的最优策略，并使用 C++ 实现了算法。