1 条题解

  • 0
    @ 2026-11-15 21:49:34

    题目分析

    梦熊主义 题解

    其实当你看到要对一个区间进行操作的时候,就要联想到区间 dp。但其实状态设计和转移也是有一定难度的

    关键观察:一个 "of" 后面删除多少,与其前、后都有关,因此考虑使用区间DP。

    状态设计

    设 f(l,r) 为闭区间 [l,r] 经过操作之后的最小长度。

    考虑转移时,我们分类讨论第一个字符是否删除:

    情况1:删除第一个字符

    条件:

    1. S[l] = 'm'
    2. 找到一个 (l,r] 内的 k,满足 S[k] = 'x'
    3. (l,k) 内的所有字符能删除,即 f(l+1,k-1) = 0

    转移:

    含义:

    • 先删除 (l,k) 区间
    • 然后删除 l 和 k 及后面的 K 个字符
    • 但不能删到负数,所以取 max{..., 0}

    情况2:不删除第一个字符

    条件:

    • 无特殊条件,任何情况均可转移

    转移:

    含义:

    • 因为第一个字符不删除,所以 l 和 (l,r] 是独立的
    • l 后面的区间最少可以剩下 f(l+1,r) 个字符
    • 再加上 l 这个字符,所以总长度为 f(l+1,r) + 1

    答案为 f(0, n-1),其中 n 是字符串长度。

    复杂度 O(n3)O(n^3),实现的时候要注意转移的顺序。

    • 1

    信息

    ID
    215
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者