金苹果岛算法题解 - C++代码实现

题目描述

你是一位代码勇者，来到了拥有神奇魔法的金苹果岛。岛上有两种苹果：

红苹果: 随处可见，食用后能提升你的代码能力，但提升效果不一，可能是正数也可能是负数。
金苹果: 非常稀有，食用后能使你的代码能力翻倍！

你现在拥有初始代码能力值为 1。苹果仙子将为你提供 n 个红苹果和 m 个金苹果，你需要吃光所有苹果。

规则：

你必须按照仙子规定的顺序吃红苹果。
你可以自由安排吃金苹果的时机，可以在吃任意红苹果之前或之后吃任意数量的金苹果。

请问，如何安排才能使你离开金苹果岛时的代码能力值最大？

输入格式

第一行输入两个正整数 n 和 m，分别代表红苹果和金苹果的数量。(n ≤ 10^5, m ≤ 10)
第二行输入 n 个整数 aᵢ，表示每个红苹果带来的代码能力提升值。(|aᵢ| ≤ 10)

输出格式

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

样例

输入 #1

6 2
1 -2 3 1 -6 5

输出 #1

解释

最优策略是先吃掉红苹果 [1, -2, 3, 1]，此时代码能力值为 4。
然后吃掉 2 个金苹果，代码能力翻倍，变为 16。
最后吃掉剩余的红苹果 [-6, 5]，最终代码能力值为 15。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> red(n);
    for (int i = 0; i < n; i++) {
        cin >> red[i];
    }
    sort(red.begin(), red.end());
    long long max_ability = 1;
    for (int i = 0; i < n; i++) {
        max_ability += red[i];
    }
    if (m == 0) {
        cout << max_ability << endl;
        return 0;
    }
    long long max_double_ability = max_ability;
    for (int i = 0; i < n; i++) {
        max_double_ability = max(max_double_ability, max_ability + red[i]);
    }
    max_double_ability <<= m;
    cout << max_double_ability << endl;
    return 0;
}

解题思路

本题结合了贪心算法和动态规划的思想。

贪心策略: 为了最大化金苹果的效果，我们应该在代码能力值较高的时候吃金苹果。因此，最优策略是在吃完所有正值的红苹果后，再吃金苹果。
动态规划: 我们可以使用动态规划来计算在吃完每个红苹果后，吃或不吃金苹果所获得的最大能力值。

代码解释

首先，我们将所有红苹果的值读入 red 数组，并对其进行排序。
然后，我们计算吃完所有红苹果后的代码能力值 max_ability。
接下来，我们遍历排序后的红苹果，计算吃完每个红苹果后，吃或不吃金苹果所获得的最大能力值 max_double_ability。
最后，我们将 max_double_ability 左移 m 位，即乘以 2 的 m 次方，得到最终的最大代码能力值。