3472. 至多 K 次操作后的最长回文子序列

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

考点

  • 区间DP
  • 回文序列

思路

一、问题抽象

给定一个长度为 \(n\) 的小写字母串 \(s\)，字符来自环状字母表 \(\{a,\dots,z\}\)。一次操作可以把某个字符变为其在字母表中的相邻字符（前一个或后一个），字母表首尾相连。

允许进行最多 \(K\) 次这样的操作，目标是：

在对字符串进行不超过 \(K\) 次操作后，得到的字符串中，最长回文子序列的长度最大是多少？

这里的“回文子序列”仅要求保持原相对顺序，不要求连续。

二、配对成本的建模

在任意回文子序列中，除去可能的中心字符，其余字符总是两两在左右对称的位置成对出现。因此，对每一对对称位置上的字符 \(s[i]\)、\(s[j]\)，若想将其放入回文子序列，就需要把这两个字符改成相同的某个字母。

由于字母表是环状的，记字符 \(c_1, c_2\) 的索引差为 \(|c_1 - c_2|\)，则这两个字符沿环相互靠拢的最少步数为： \[ \operatorname{dist}(c_1, c_2) = \min\bigl(|c_1 - c_2|,\ 26 - |c_1 - c_2|\bigr) \] 这个值就是：

“把 \(s[i]\) 和 \(s[j]\) 修改成同一个字母所需的最小操作次数”。

注意：最终它们被改成哪个字母完全不重要，只要两者相同即可。因此可以把修改过程压缩为一个局部成本 \(\operatorname{dist}(s[i], s[j])\)。

三、状态定义：恰好使用 \(k\) 次操作

设三维 DP 状态为： \[ f[k][i][j] \] 含义为：

在区间 \([i, j]\) 内，恰好使用 \(k\) 次操作（这些操作只发生在 \([i,j]\) 上），能得到的最长回文子序列长度。

其中：

  • \(0 \le k \le K\),
  • \(1 \le i \le j \le n\)。

需要特别说明的是：在这个定义下，“恰好使用 \(k\) 次操作”允许空耗操作，即可以在某个字符上做若干“多余”的循环修改（例如转一圈又转回来），不会改变回文长度。所以从最终答案的角度看，“恰好使用 \(k\) 次（允许空耗）”与“最多使用 \(k\) 次”是等价的。

四、边界条件

对于任意单个字符区间 \([i,i]\)：

  • 无论做多少（包括 0 次）操作，这个字符本身始终可以构成长度为 1 的回文子序列。
  • 多出来的操作可以全部空耗在这个字符上。

因此有： \[ f[k][i][i] = 1 \quad \forall\ 0 \le k \le K,\ 1 \le i \le n. \]

五、状态转移

考虑区间 \([i, j]\)（其中 \(i < j\)），在该区间内恰好使用 \(k\) 次操作。设： \[ d = \operatorname{dist}(s[i], s[j]) = \min\bigl(|s[i] - s[j]|,\ 26 - |s[i] - s[j]|\bigr). \]

5.1 不将两端同时放入回文（跳过端点）

可以选择不把位置 \(i\) 纳入回文，只在 \([i+1, j]\) 中构造回文；也可以选择不把位置 \(j\) 纳入回文，只在 \([i, j-1]\) 中构造回文。这两种选择都不必消耗新操作，只是把“恰好 \(k\) 次操作”的使用全部留给子区间。

因此有转移： \[ f[k][i][j] \ge \max\bigl(f[k][i+1][j],\ f[k][i][j-1]\bigr). \] 这里的语义是：

在 \([i,j]\) 区间内恰好使用 \(k\) 次操作时，如果决定不使用端点 \(i\)（或 \(j\)）构造回文，就把这 \(k\) 次操作全留给内部区间 \([i+1,j]\)（或 \([i,j-1]\)）去使用或空耗。

5.2 将两端字符配成一对

若希望把 \(s[i]\) 和 \(s[j]\) 作为回文子序列的一对对称字符，则需要：

  1. 在区间 \([i,j]\) 内的操作总数为 \(k\)；
  2. 其中有 \(d\) 次操作用于让 \(s[i]\) 和 \(s[j]\) 变成同一个字符；
  3. 剩余 \(k-d\) 次操作可以用于中间区间 \([i+1, j-1]\) 内（包括必要修改和空耗）。

只要 \(k \ge d\)，就可以这样配对两端，因此得到： \[ f[k][i][j] \ge f[k - d][i+1][j-1] + 2. \] 无论 \(s[i]\) 与 \(s[j]\) 最初是否相等，这一式统一处理了“配成一对”的情况：

  • 若本来相等，则 \(d = 0\)，不需要额外操作；
  • 若本来不等，则 \(d > 0\)，需要消耗相应的操作次数。

5.3 综合转移方程

综合“跳过端点”和“两端配对”两种决策，对于每个 \(k, i, j\) 有： \[ f[k][i][j] = \max\left( f[k][i+1][j],\ f[k][i][j-1],\ \mathbf{1}_{k \ge d}\cdot\bigl(f[k-d][i+1][j-1] + 2\bigr) \right), \] 其中 \(d = \operatorname{dist}(s[i], s[j])\)。

在实现中，可以写成：

  • 先用 max(f[k][i+1][j], f[k][i][j-1]) 初始化；
  • 若 k >= d，再尝试用 f[k-d][i+1][j-1] + 2 更新。

六、遍历顺序

要保证所有被依赖的子状态已经计算完毕，典型做法是：

  1. 先处理长度为 1 的区间，已经在初始化中完成；
  2. 对每个操作次数 \(k = 0, 1, \dots, K\)：
    • 对区间长度 len = 2, 3, ..., n：
      • 枚举左端点 i，令 j = i + len - 1：
        • 按上述转移更新 f[k][i][j]。

在这个顺序下：

  • f[k][i+1][j] 与 f[k][i][j-1] 来自同一个 \(k\) 和更短的区间；
  • f[k-d][i+1][j-1] 来自更小的 \(k-d\) 和更短的区间；
  • 均已经被计算过，因此是合法的拓扑顺序。

七、从“恰好 \(k\) 次”到“最多 \(K\) 次”

由于状态定义允许在任意字符上空耗操作：

  • 对于任意在区间 \([1,n]\) 内使用不超过 \(k\) 次有效修改的方案，都可以通过额外添加若干空耗操作，使其变成“恰好使用 \(k\) 次”的方案，而不改变回文长度。

因此，在全局区间 \([1,n]\) 上，“恰好 \(k\) 次”所能达到的最优值与“最多 \(k\) 次”所能达到的最优值是一致的，只是数值上它们被记录在不同的 \(k\) 层上。

最终答案取： \[ \max_{0 \le k \le K} f[k][1][n] \] 即在所有“恰好使用 \(k\) 次操作（含空耗）”的方案中，选择最长回文子序列长度的最大值，这与题目要求的“最多 \(K\) 次操作”是等价的。

八、时间与空间复杂度

  • 状态数量为： \[ O\bigl((K+1) \cdot n^2\bigr) \]

  • 每个状态的转移是 \(O(1)\)。

  • 因此时间复杂度为： \[ O(K n^2) \]

  • 空间复杂度为： \[ O(K n^2) \]

九、AC代码

下面是对应上述建模的 C++ 实现，基于题意约束采用三维数组，状态语义为“在 \([i,j]\) 内恰好使用 \(k\) 次操作（允许空耗）所得的 LPS 长度”。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
    static const int maxn = 2e2 + 5;

    int longestPalindromicSubsequence(string s, int K) {
        // f[k][i][j]:
        // 在区间 [i, j] 内，恰好使用 k 次操作（允许空耗），
        // 能得到的最长回文子序列长度。
        int f[maxn][maxn][maxn] = {};

        int n = s.size();

        // ---- 初始化：长度为 1 的所有子区间 ----
        // 单个字符始终可以构成长度为 1 的回文子序列，
        // 多出来的操作可以空耗在该字符上，因此对所有 k 都为 1。
        for (int k = 0; k <= K; ++k) {
            for (int i = 1; i <= n; ++i) {
                f[k][i][i] = 1;
            }
        }

        // ---- 区间 DP ----
        // 枚举操作次数 k
        for (int k = 0; k <= K; ++k) {
            // 按区间长度从小到大枚举
            for (int len = 2; len <= n; ++len) {
                // 枚举左端点 i，右端点 j = i + len - 1
                for (int i = 1; i + len - 1 <= n; ++i) {
                    int j = i + len - 1;

                    // 若两端字符相同，可以不花任何操作数，
                    // 直接把这两个字符作为一对加入回文。
                    if (s[i - 1] == s[j - 1]) {
                        // 注意这里用的是同一层 k，因为不需要消耗操作。
                        f[k][i][j] = f[k][i + 1][j - 1] + 2;
                    } else {
                        // 首先考虑不把 s[i] 或 s[j] 放入回文：
                        // 1) 跳过 i：只在 [i+1, j] 中构造
                        // 2) 跳过 j：只在 [i, j-1] 中构造
                        // 这两种情况都不新消耗操作，总操作次数仍为 k。
                        f[k][i][j] = max(f[k][i + 1][j], f[k][i][j - 1]);

                        // 计算把 s[i] 与 s[j] 变为同一字符所需的最小操作数 d
                        int d = abs(s[i - 1] - s[j - 1]);
                        d = min(d, 26 - d);  // 环状字母表上的最短距离

                        // 若当前区间被要求恰好使用 k 次操作，
                        // 且其中有 d 次操作用于这对端点，
                        // 则剩余的 k-d 次操作可以用在 [i+1, j-1] 内（包含空耗）。
                        if (k - d >= 0) {
                            f[k][i][j] = max(
                                f[k][i][j],
                                f[k - d][i + 1][j - 1] + 2
                            );
                        }
                    }
                }
            }
        }

        // ---- 取答案 ----
        // 在“恰好使用 k 次操作”的所有层中取最大值。
        // 由于允许空耗，这与“最多使用 K 次操作”的最优值等价。
        int ans = 0;
        for (int k = 0; k <= K; ++k)
            ans = max(ans, f[k][1][n]);

        return ans;
    }
};