题解：B4336 [中山市赛 2023] 永别

AFO_Lzx · 2025-06-14 13:00:57 · 题解

退役后的第一篇题解，OI，永别了。

很显然应该用 O(n^2) 的做法，区间 DP 应该是个不错的选择。

• 设计状态：设 f_{i,j} 为从 i 到 j 中最长回文子序列的长度。

• 确定答案：很显然，因为字符串的下标从 0 开始，所以答案为 f_{0,n-1}，也就是从 0 到 n-1 中最长回文子序列的长度。

• 状态转移：

  ① 当 s_i=s_j 时，可以构成一个回文子序列，f_{i,j}=f_{i+1,j-1}+2。

  ② 当 s_i\ne s_j 时，不能构成，f_{i,j}=\max(f_{i+1,j},f_{i,j-1})。

• 初始化：很显然，长度为 1 的区间的最长回文子序列的长度为 1，故 f_{i,i}=1。

可以通过本题的代码如下：

#include<bits/stdc++.h>
using ll = long long;
using namespace std;

const int N = 1e3 + 5;
int n, f[N][N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    string s;
    cin >> s;

    for (int i = 0; i < n; i++) {
        f[i][i] = 1;
    }
    for (int l = 2; l <= n; l++) {
        for (int i = 0; i < n - l + 1; i++) {
            int j = i + l - 1;
            if (s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;
            else f[i][j] = max(f[i][j - 1], f[i + 1][j]);
        }
    }
    cout << f[0][n - 1] << '\n';
    return 0;
}