2919. 使数组变美的最小增量运算数

发表于 分类于 阅读次数： Waline： 本文字数： 801 阅读时长 ≈ 3 分钟

考点

  • 状态机DP
  • 状态设计

思路

1. 问题抽象

对于数组 nums，我们希望通过最少的自增操作，使得所有长度不小于 3 的连续子数组的最大值都满足： \[ \max(\text{subarray}) \ge k. \] 等价表述（关键化简）：

整个数组中不允许出现长度 ≥ 3 的连续段，使该段内所有元素均 < k。

因此问题转化为：

如何最少地将部分位置提升到 ≥ k，使整个数组不存在连续 3 个位置都 < k 的情况。

2. DP 状态设计：记录“尾部连续 < k 的个数”

对任意前缀 \([1..i]\)，我们只关心最后有多少个连续的元素仍然是 < k。因为一旦出现连续 3 个 < k，就会违例。

定义二维 DP： \[ f[i][d] = \text{使前 } i \text{ 个元素满足约束，且尾部连续 } d \text{ 个元素}<k\text{ 的最小代价}, \] 其中 \[ d \in \{0,1,2\}. \] 三种状态含义：

  • \(d = 0\)：第 \(i\) 个位置最终被提升为 \(\ge k\)。
  • \(d = 1\)：第 \(i\) 个位置仍 < k，但第 \(i-1\) 是 \(\ge k\)。
  • \(d = 2\)：第 \(i\) 个位置仍 < k，且第 \(i-1\) 也 < k，但第 \(i-2\) 是 \(\ge k\)。

禁止出现 \(d = 3\)，因为那意味着长度为 3 的违例段。

3. 初始条件（重点）

长度为 0 的前缀定义为合法： \[ f[0][0] = 0, \qquad f[0][1] = f[0][2] = +\infty. \] 理由：

  • 空前缀没有连续 < k 的元素，因此尾部 < k 个数为 0，成本为 0。
  • 不可能在空前缀时尾部连续 1 个或 2 个 < k，因此设为不可达的正无穷。

这一初始化是整个 DP 能否正确运行的关键。

4. 转移方程

处理第 \(i\) 个元素，记其原值为 \(x = nums[i-1]\)，将其提升到 \(k\) 的成本为： \[ \text{cost}_i = \max(0,\ k - x). \]

4.1 选择把位置 \(i\) 提升到 \(\ge k\)

无论之前尾部连续 < k 为 0、1 或 2，现在都变为 0： \[ f[i][0] = \min\{ f[i-1][0],\ f[i-1][1],\ f[i-1][2] \} + \text{cost}_i. \]

4.2 选择不提升位置 \(i\)（即让它保持 < k）

由于此时元素最终需为 < k，因此它的尾部计数会在原基础上 +1： \[ f[i][1] = f[i-1][0], \qquad f[i][2] = f[i-1][1]. \] 不能从 \(f[i-1][2]\) 推出 \(f[i][3]\)，因为 \(d=3\) 是非法状态。

5. 答案

整个数组扫描完后，任意合法结尾状态均可接受，因此答案为： \[ \boxed{ \min\{ f[n][0],\ f[n][1],\ f[n][2] \} } \]

6. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    static const int maxn = 1e5 + 5, inf = 0x3f3f3f3f;
    long long minIncrementOperations(vector<int>& nums, int k) {
        long long f[maxn][3];
        int n = nums.size();
        f[0][0] = 0;
        f[0][1] = f[0][2] = inf;
        for (int i = 1; i <= n; ++i) {
            f[i][0] = min(f[i - 1][0], min(f[i - 1][1], f[i - 1][2])) +
                      max(0, k - nums[i - 1]);
            f[i][1] = f[i - 1][0];
            f[i][2] = f[i - 1][1];
        }
        return min(f[n][0], min(f[n][1], f[n][2]));
    }
};

滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 1e5 + 5, inf = 0x3f3f3f3f;
    long long minIncrementOperations(vector<int>& nums, int k) {
        int n = nums.size();
        long long a = 0, b = inf, c = inf;
        for (int i = 1; i <= n; ++i) {
            long long ta, tb, tc;
            ta = min(a, min(b, c)) + max(0, k - nums[i - 1]);
            tb = a;
            tc = b;
            a = ta, b = tb, c = tc;
        }
        return min(a, min(b, c));
    }
};