2167. 移除所有载有违禁货物车厢所需的最少时间

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 状态机DP
  • 前后缀分解

思路

一、问题抽象

给定一个长度为 \(n\) 的二进制字符串 \(s\)，其中：

  • '1' 表示该车包含非法货物；
  • '0' 表示合法车辆。

允许以下两种操作：

  1. 端点删除：从字符串的左端或右端删除一辆车，代价为 \(1\)；
  2. 单点删除：删除任意一辆 '1'，代价为 \(2\)。

目标是：以最小总代价移除所有 '1'（可以保留 '0'）。

二、操作的结构性观察

任意一种合法方案，最终都可以视为以下三部分的组合：

  1. 从左端删除若干辆车；
  2. 从右端删除若干辆车；
  3. 对剩余区间中的 '1' 使用单点删除。

端点删除的效果具有“区间收缩”的性质，而单点删除只作用于 '1'。 这使得问题具有明显的 动态规划结构。

三、二维状态机 DP（核心方法）

1. 状态定义

令 \(f[i][k]\) 表示处理完前 \(i\) 个字符后的最小代价，其中：

  • \(f[i][0]\)：前 \(i\) 个字符 全部从左端删除；
  • \(f[i][1]\)：前 \(i\) 个字符中 所有 '1' 已被清除，允许保留 '0'；
  • \(f[i][2]\)：已经完成“前缀清除”，并开始用 右端删除的方式继续处理。

初始条件： \[ f[0][0] = 0,\quad f[0][1] = 0,\quad f[0][2] = +\infty \]

2. 状态转移

（1）状态 0：全部左端删除

\[ f[i][0] = f[i-1][0] + 1 \]

（2）状态 1：清除所有 '1'

  • 若 \(s[i-1] = '0'\)，不需要额外操作：

\[ f[i][1] = f[i-1][1] \]

  • 若 \(s[i-1] = '1'\)，有两种选择：
    • 从左端删除该字符：代价 \(f[i-1][0] + 1\)
    • 单点删除该 '1'：代价 \(f[i-1][1] + 2\)

取最小值： \[ f[i][1] = \min\big(f[i-1][0] + 1,\; f[i-1][1] + 2\big) \]

（3）状态 2：开始右端删除

一旦进入状态 2，后续只能通过端点删除推进： \[ f[i][2] = \min\big(f[i-1][1],\; f[i-1][2]\big) + 1 \]

3. 最终答案

\[ \text{ans} = \min\big(f[n][0],\; f[n][1],\; f[n][2]\big) \]

4. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    static const int maxn = 2e5 + 5;

    int minimumTime(string s) {
        int f[maxn][3];
        int n = s.size();

        // 初始化：处理 0 个字符
        f[0][0] = 0;                 // 全删
        f[0][1] = 0;                 // 已清除所有 '1'
        f[0][2] = INT_MAX >> 1;      // 尚未开始右端删除，不可达

        for (int i = 1; i <= n; ++i) {
            // 状态 0：前 i 个字符全部从左端删除
            f[i][0] = f[i - 1][0] + 1;

            // 状态 1：清除前 i 个字符中的所有 '1'
            if (s[i - 1] == '1') {
                // 两种方式：
                // 1) 从左端删除该字符
                // 2) 单点删除该 '1'
                f[i][1] = min(f[i - 1][0] + 1, f[i - 1][1] + 2);
            } else {
                // '0' 不需要处理
                f[i][1] = f[i - 1][1];
            }

            // 状态 2：已经进入“右端删除阶段”
            f[i][2] = min(f[i - 1][1], f[i - 1][2]) + 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
class Solution {
public:
    static const int maxn = 2e5 + 5;
    int minimumTime(string s) {
        int n = s.size();
        int f0 = 0, f1 = 0, f2 = INT_MAX >> 1;
        for (int i = 1; i <= n; ++i) {
            int new_f0 = f0 + 1;
            int new_f1 = s[i - 1] == '1' ? min(f0 + 1, f1 + 2) : f1;
            int new_f2 = min(f1, f2) + 1;
            f0 = new_f0, f1 = new_f1, f2 = new_f2;
        }
        return min(f0, min(f1, f2));
    }
};

四、前后缀分解（等价但更简洁）

1. 前缀定义

令 \(l[i]\) 表示：清除前 \(i\) 个字符中所有 '1' 的最小代价。 \[ l[0] = 0 \] 递推： \[ l[i] = \begin{cases} \min(i,\; l[i-1]) & s[i-1] = '0' \\ \min(i,\; l[i-1] + 2) & s[i-1] = '1' \end{cases} \] 其中：

  • \(i\)：表示直接把前缀整体删除；
  • \(l[i-1] + 2\)：表示单点删除该 '1'。

2. 后缀定义

令 \(r[i]\) 表示：清除区间 \([i, n]\) 中所有 '1' 的最小代价。 \[ r[n+1] = 0 \] 递推： \[ r[i] = \begin{cases} \min(n-i+1,\; r[i+1]) & s[i-1] = '0' \\ \min(n-i+1,\; r[i+1] + 2) & s[i-1] = '1' \end{cases} \]

3. 切分点合并

枚举切分点 \(i\)，前缀用 \(l[i]\)，后缀用 \(r[i+1]\)： \[ \text{ans} = \min_{0 \le i \le n} \big( l[i] + r[i+1] \big) \]

4. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    static const int maxn = 2e5 + 5;

    int minimumTime(string s) {
        int n = s.size();
        int l[maxn], r[maxn];

        // l[i]: 清除前 i 个字符中所有 '1' 的最小代价
        l[0] = 0;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == '1')
                l[i] = min(i, l[i - 1] + 2);
            else
                l[i] = min(i, l[i - 1]);
        }

        // r[i]: 清除区间 [i..n] 中所有 '1' 的最小代价
        r[n + 1] = 0;
        for (int i = n; i >= 1; --i) {
            if (s[i - 1] == '1')
                r[i] = min(n - i + 1, r[i + 1] + 2);
            else
                r[i] = min(n - i + 1, r[i + 1]);
        }

        // 枚举切分点
        int ans = INT_MAX >> 1;
        for (int i = 0; i <= n; ++i) {
            ans = min(ans, l[i] + r[i + 1]);
        }
        return ans;
    }
};

五、两种方法的等价性说明

  • 二维状态机中的 \(f[i][1]\)，本质等价于前缀数组 \(l[i]\)；
  • 状态 \(f[i][2]\) 的转移，等价于枚举一个切分点，将后缀整体通过端点删除；
  • 因此，状态机 DP 与前后缀分解在数学上完全等价，只是实现方式不同。