题目描述

给你一个整数数组 nums 和三个整数 k、op1 和 op2。

你可以对 nums 执行以下操作：

• 操作 1：选择一个下标 i，将 nums[i] 除以 2，并 向上取整 到最接近的整数。你最多可以执行此操作 op1 次，并且每个下标最多只能执行一次。
• 操作 2：选择一个下标 i，仅当 nums[i] 大于或等于 k 时，从 nums[i] 中减去 k。你最多可以执行此操作 op2 次，并且每个下标最多只能执行一次。

注意： 两种操作可以应用于同一下标，但每种操作最多只能应用一次。

返回在执行任意次数的操作后，nums 中所有元素的 最小 可能 和。

样例

输入： nums = [2,8,3,19,3], k = 3, op1 = 1, op2 = 1

输出： 23

解释：

对 nums[1] = 8 应用操作 2，使 nums[1] = 5。
对 nums[3] = 19 应用操作 1，使 nums[3] = 10。
结果数组变为 [2, 5, 3, 10, 3]，在应用操作后具有最小可能和 23。

输入： nums = [2,4,3], k = 3, op1 = 2, op2 = 1

输出： 3

解释：

对 nums[0] = 2 应用操作 1，使 nums[0] = 1。
对 nums[1] = 4 应用操作 1，使 nums[1] = 2。
对 nums[2] = 3 应用操作 2，使 nums[2] = 0。
结果数组变为 [1, 2, 0]，在应用操作后具有最小可能和 3。

限制

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^5
• 0 <= k <= 10^5
• 0 <= op1, op2 <= nums.length

算法

(动态规划) $O(n^3)$

1. 由于每个数字的操作都是独立的，考虑动态规划求解。
2. 设状态 $f(i, x, y)$ 表示考虑了前 $i$ 个数字，使用了 $x$ 次操作 1，$y$ 次操作 2 后可以得到的最小和。其中 $i$ 的有效下标从 $1$ 开始。
3. 初始时，$f(0, 0, 0) = 0$，其余为 $+\infty$ 待定。
4. 转移时，对于 $f(i, x, y)$，这个数字可以不操作，则转移 $f(i - 1, x, y) + nums(i)$，可以使用第一种操作，转移 $f(i - 1, x - 1, y) + (nums(i) + 1) / 2$，同理也可以使用第二种操作或者两种操作都使用，注意两种操作都使用的时候，还需要考虑先使用哪一种操作。这五种操作中取最小值。
5. 最终答案为 $\min{f(n, x, y)}$。
6. 由于每一维状态都和上一维有关，所以可以倒序枚举省略掉第一维的状态表示。

时间复杂度

• 状态数为 $O(n^3)$，转移时间为常数，故总时间复杂度为 $O(n^3)$。

空间复杂度

• 空间优化后，需要 $O(n^2)$ 的额外空间存储状态。

C++ 代码

const int N = 110;
const int INF = 1000000000;

class Solution {
private:
    int f[N][N];

public:
    int minArraySum(vector<int>& nums, int k, int op1, int op2) {
        const int n = nums.size();

        for (int j = 0; j <= op1; j++)
            for (int k = 0; k <= op2; k++)
                f[j][k] = INF;

        f[0][0] = 0;

        for (int i = 0; i < n; i++) {
            int t = nums[i];

            for (int x = op1; x >= 0; x--)
                for (int y = op2; y >= 0; y--) {
                    int &p = f[x][y];

                    p += t;

                    if (x > 0)
                        p = min(p, f[x - 1][y] + (t + 1) / 2);

                    if (y > 0 && t >= k)
                        p = min(p, f[x][y - 1] + t - k);

                    if (x > 0 && y > 0) {
                        if (t >= k)
                            p = min(p, f[x - 1][y - 1] + (t - k + 1) / 2);

                        if ((t + 1) / 2 >= k)
                            p = min(p, f[x - 1][y - 1] + (t + 1) / 2 - k);
                    }
                }
        }

        int ans = INF;
        for (int x = 0; x <= op1; x++)
            for (int y = 0; y <= op2; y++)
                ans = min(ans, f[x][y]);

        return ans;
    }
};