编辑距离与状态机模型

import sys

data = sys.stdin.read().split()               # 按 token 总数切分：空行不会让下标错位
n, m = int(data[0]), int(data[1])
ref = data[2:2 + n]                           # 参考序列（n 个 token）
hyp = data[2 + n:2 + n + m]                   # 识别序列（m 个 token）
# ① d[i][j] = 识别序列前 j 个 token 变成参考序列前 i 个 token 的最少编辑次数；只保留上一行 prev 和本行 cur
prev = list(range(m + 1))                     # ③ d[0][j] = j：参考为空，删掉 j 个识别 token
for i in range(1, n + 1):                     # ④ 逐行
    cur = [i] + [0] * m                       # d[i][0] = i：识别为空，插入 i 个参考 token
    a = ref[i - 1]
    for j in range(1, m + 1):
        if a == hyp[j - 1]:
            best = prev[j - 1]                # ② 相同：走对角，不加操作
        else:
            best = prev[j - 1] + 1            # 替换
        if prev[j] + 1 < best:                # 上方：插入一个参考 token
            best = prev[j] + 1
        if cur[j - 1] + 1 < best:             # 左方：删除一个识别 token
            best = cur[j - 1] + 1
        cur[j] = best
    prev = cur
d = prev[m]                                   # ⑤ 右下角
print(d)
if n > 0:
    r = (20000 * d + n) // (2 * n)            # CER × 10⁴ 四舍五入：全程整数
else:
    r = d * 10000                             # 参考为空：题目规定 CER 数值等于距离本身
print(f"{r // 10000}.{r % 10000:04d}")

滚动两行：prev 是上一行、cur 是本行；2000×2000 是 4×10⁶ 次转移，内层只做整数比较。自测建议：题面两组示例、第 05 节三条要求对应的用例、32 个 token 错 1 个（0.0313）、CER 大于 1 的例子（1.3333）；想进一步验证，可与二维表写法对拍随机短序列。

import sys

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
NEG = float("-inf")
dp = [NEG] * (k + 1)                          # ① dp[r] = 本轮结束、冷却还剩 r 轮时的最大总收益；不可达 = -∞
dp[0] = 0                                     # ③ 第 1 轮开始前：无冷却、收益 0，是唯一合法起点
for i in range(n):                            # ④ 逐轮
    a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
    new = [NEG] * (k + 1)
    for r in range(1, k + 1):                 # ② 冷却中只能休息：剩 r 轮 → 剩 r-1 轮
        if dp[r] > new[r - 1]:
            new[r - 1] = dp[r]
    if dp[0] > new[0]:                        # 无冷却时休息
        new[0] = dp[0]
    if dp[0] + a > new[0]:                    # 无冷却时接常规
        new[0] = dp[0] + a
    if dp[0] + b > new[k]:                    # 无冷却时接加急：之后冷却 k 轮（k = 0 时落回 new[0]）
        new[k] = dp[0] + b
    dp = new
print(int(max(dp)))                           # ⑤ 最后一轮结束时任何冷却状态都合法

自测建议：题面两组示例（18 / 18）、全负（0）、k = 0（11）、单轮加急（7）；n = 200000、k = 10 时约 2.2×10⁶ 次转移。想进一步验证，可写「枚举每轮三种选择」的暴力对拍短输入。

def edit_dist(a: str, b: str) -> int:
    n, m = len(a), len(b)
    d = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        d[i][0] = i                          # 目标为空：删除 i 次
    for j in range(1, m + 1):
        d[0][j] = j                          # 原串为空：插入 j 次
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                d[i][j] = d[i - 1][j - 1]    # 相同：走对角，不加操作
            else:
                d[i][j] = min(d[i - 1][j - 1], d[i - 1][j], d[i][j - 1]) + 1   # 替换 / 删除 / 插入
    return d[n][m]

assert edit_dist("cat", "cut") == 1   # a→u 一次替换
assert edit_dist("abc", "") == 3      # 三次删除：第 0 列初始化在这里检验
assert edit_dist("", "ab") == 2       # 两次插入：第 0 行初始化
assert edit_dist("ab", "ab") == 0
assert edit_dist("ab", "ba") == 2     # 第 10 节练习 1 的表
assert edit_dist("sunday", "saturday") == 3

两个空串断言专门检验第 0 行、第 0 列。

def cooldown_max(k, rows, start_cool=0):
    NEG = float("-inf")
    dp = [NEG] * (k + 1)                     # dp[r] = 本轮结束、冷却还剩 r 轮时的最大收益；不可达 = -∞
    dp[start_cool] = 0                       # 唯一合法起点：开局冷却剩 start_cool 轮（AI026 是 0）
    for a, b in rows:
        new = [NEG] * (k + 1)
        for r in range(1, k + 1):
            new[r - 1] = max(new[r - 1], dp[r])       # 冷却中只能休息
        new[0] = max(new[0], dp[0], dp[0] + a)        # 无冷却：休息 / 常规
        new[k] = max(new[k], dp[0] + b)               # 无冷却：加急，之后冷却 k 轮
        dp = new
    return int(max(dp))

assert cooldown_max(1, [(2, 9), (6, 1), (2, 9), (6, 1)]) == 18   # AI026 题面示例 1
assert cooldown_max(2, [(1, 10), (8, 0), (9, 1)]) == 18          # 示例 2：三轮都接常规
assert cooldown_max(1, [(-5, -2), (-1, -1), (-3, -9)]) == 0     # 全负：全部休息
assert cooldown_max(0, [(1, 5), (2, 1), (-1, 4)]) == 11          # k = 0：每轮取 max(a, b, 0)
assert cooldown_max(3, [(-2, 7)]) == 7                           # 最后一轮接加急也合法
assert cooldown_max(2, [(1, 10), (8, 0), (9, 1)], start_cool=2) == 9   # 变式：开局冷却 2 轮，只能做第 3 轮

变式答案 9（前两轮只能休息，第 3 轮取 max(9, 1)）。把 dp = [NEG] * (k + 1); dp[start_cool] = 0 改成全 0，变式会输出 18——不可达的 dp[0] = 0 让第 1 轮就能接任务。