[R61D] 01串分割

数据规模：$1 \le n \le 10^6$，$s$ 仅由 0 和 1 组成，$1 \le a_i \le 10^9$。

思路

所有合法块 1、01、001 都以 1 结尾，所以合法字符串的末尾必定是 1。先说明一个关键事实：最优方案中不需要把 1 改成 0。若某个方案把位置 $p$ 的 1 改成了 0，$p$ 必位于某个块的内部（块以 1 结尾，故 $p$ 不是块尾）。把 $p$ 改回 1 后，它所在的块会变成 11、101 或 011，三者都能重新分割成两个合法块（1+1、1+01、01+1），整个串依然合法，且代价严格减少。因此只需考虑把 0 改成 1 的操作。

于是可以做线性 DP。设 $dp[i]$ 表示把前缀 $s[1..i]$ 变为合法字符串、且第 $i$ 位为 1 的最小代价，$dp[0]=0$。按最后一块的形态转移：

• 最后一块为 1：从 $dp[i-1]$ 转移；
• 最后一块为 01：从 $dp[i-2]$ 转移；
• 最后一块为 001：从 $dp[i-3]$ 转移。

三种块都以 1 结尾，因此每个候选都只需额外处理第 $i$ 位：若 $s_i=0$，则要花 $a_i$ 把它翻成 1；若 $s_i=1$，保持原样即可。转移方程为

$dp[i]=\min(dp[i-1],\,dp[i-2],\,dp[i-3])+a_i\cdot[s_i=0],$

其中 $[s_i=0]$ 为 $1$ 当且仅当 $s_i$ 是 0；下标越界的项（$i=1$、$i=2$ 时）不参与转移。由于所有块都以 1 结尾，整个串合法等价于前缀 $s[1..n]$ 合法，答案就是 $dp[n]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

仓颉实现

import std.env.*
import std.convert.*

main(): Int64 {
    let reader = getStdIn()
    let n = Int64.parse(reader.readln().getOrThrow().split(" ", removeEmpty: true)[0])
    let s = reader.readln().getOrThrow().toRuneArray()
    let a = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })

    // dp[i]: 前缀 s[0..i) 变为合法字符串且第 i 个字符为 '1' 的最小代价
    let dp = Array<Int64>(n + 1, { _ => 0 })
    var i = 1
    while (i <= n) {
        var best = dp[i - 1]
        if (i >= 2 && dp[i - 2] < best) {
            best = dp[i - 2]
        }
        if (i >= 3 && dp[i - 3] < best) {
            best = dp[i - 3]
        }
        if (s[i - 1] == r'0') {
            best += a[i - 1]
        }
        dp[i] = best
        i += 1
    }
    println(dp[n])
    return 0
}

要点

• 翻转方向：所有块都以 1 结尾，任何把 1 改成 0 的操作都可以省去——改回 1 后所在块变为 11、101 或 011，仍能重新分割成两个合法块，串依然合法且代价更小，所以只把 0 翻成 1 即可。
• 转移边界：$i=1$ 时只有 1 块可用，$i=2$ 时可用 1 和 01，$i \ge 3$ 时三种块才俱全，实现时用 i >= 2、i >= 3 的条件跳过不可达项。
• 合法串末尾必为 1，答案即 $dp[n]$，不需要对末位再做额外处理。