B - 挑选数字@qwertyu c++

Question

给定一个长度为
n 的数组，需要对数组进行
k 次如下操作：

挑选数组中的一个元素，把它移除掉，并把这个值作为获取到的价值，同时会付出相应的代价，就是把数组中剩下的所有元素都减去2，但是元素最小只能变成0。
问最终
k 次操作下来之后，能够获取到的最大价值是多少？

Answer 1

EternalLBZ 晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

问题可以通过动态规划来解决。下面是解决问题的思路：

1. 创建一个 dp 数组，用来保存每个操作下的最大价值。
2. dp[i] 表示进行 i 次操作后能够获取到的最大价值。
3. 初始化 dp 数组，dp[0] = 0。
4. 遍历 1 到 k，对于每个操作 i：
   • 遍历数组，对于数组中的每个元素 arr[j]，将其移除，并将剩下的元素都减去2，保证最小值为0。
   • 计算移除元素后剩下的元素的和，加上移除的元素值，得到该操作下的总价值。
   • 更新 dp[i] 为当前操作下的总价值和之前操作下的最大价值中的较大值。
5. 返回 dp[k]，即 k 次操作下的最大价值。

代码实现：

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

int getMaxValue(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(k+1, 0); // dp数组，初始值都为0

    for (int i = 1; i <= k; i++) {
        int maxValue = 0; // 当前操作下的最大价值

        for (int j = 0; j < n; j++) {
            int value = nums[j]; // 移除的元素值
            int sum = 0; // 移除元素后剩下元素的和

            for (int m = 0; m < n; m++) {
                if (m != j) {
                    nums[m] -= 2; // 将剩下的元素都减去2
                    if (nums[m] < 0) nums[m] = 0; // 元素最小值为0
                    sum += nums[m];
                }
            }

            int totalValue = value + sum; // 当前操作下的总价值
            maxValue = max(maxValue, totalValue); // 更新最大价值

            // 还原数组的值
            for (int m = 0; m < n; m++) {
                if (m != j) {
                    nums[m] += 2;
                }
            }
        }

        dp[i] = maxValue;
    }

    return dp[k];
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int maxValue = getMaxValue(nums, k);
    cout << maxValue << endl;
    return 0;
}

时间复杂度分析：每次操作都需要对数组进行遍历，所以时间复杂度为 O(kn^2)。

希望能帮到你！