Oiclass P1928 题解

这道题简直拓宽了回文这个词的定义

天哪，我见回文数，回文分解，回文日，还真的没有见过回文词，而且这个词还毫无任何美感可言，其他回文可都是很优雅的呀。不吐槽了，进入正题

1. 划分阶段

这里定义两个字符串，\(a\) 和 \(b\) ，\(a\) 是输入的字符串，\(b\) 是 \(a\) 的反串。对于这两个字符串，一共有 \(2 \times a.length()\) 种状态，也可以说有 \(a.length() + b.length()\) 种状态

2. 确定状态和状态变量

状态变量用一个二维数组 \(f\) ，对于一个状态 \(f_{i,\ j}\) 他表示的是字符串 \(a\) 的前 \(i\) 个字符的子串和字符串 \(b\) 的前 \(j\) 个字符最长公共子序列的长度，额，为什么是最长公共子序列呢？我们可以发现，对于这两个字符串，他们的最长公共子序列实际上就是可以回文的部分，通过计算这一部分，我们就可以反向计算出我们需要添加多少个字符 从而使这个字符串整个变得回文。

3. 确定状态转移方程

直接复制粘贴 LCS 的就 OK 了，简单贴一下吧：

决策很简单呢，如果相同，那么就 \(+1\) 如果不同，那么就选择复制 \(f_{i-1,\ j}\) 和 \(f_{i,\ j-1}\) 中大的那一个，很简单，写出方程如下： \[ f_{i,\ j} = \left\{ \begin{array}{lr} a_i = b_j\ \ \ \ f_{i - 1,\ j-1} + 1\\ a_i ≠ b_j\ \ \ \ \max(f_{i-1,\ j},\ f_{i,\ j-1}) \end{array} \right. \]

4. 边界

对于这道题，边界也是非常简单，和 LCS 一模一样，根本不用赋值，这是在上一篇中的解释：

初始值想都不用想，全都是 蛋（\(0\)），那么也就很简单了，什么都不用干，只需要创建数组，完事儿

额，好像和没有解释一样，还是讲一下吧。你想一下，我们的 LCS 在什么字符都没有，也就是 \(f_{i,\ 0}\) 和 \(f_{0,\ i}\) 的时候，他必定没有任何字符可以与他形成最长公共子序列，所以这两列（行）就一定是 \(0\) 而有因为全局数组的初始值就是 \(0\) 所以什么都不需要干。

5. 实现

实现依旧是很简单，实际上只需要把 LCS 的代码稍加修改即可，也就是把 \(b\) 串设定为 \(a\) 串的反串，输出的时候输出 \(a.length()-f_{a.length(),\ a.length()}\) 即可，而又因为题目中已经给到了我们字符串的长度，所以只需要输出 \(n-f_{n,\ n}\) 即可。除了不是很优雅，这道题简直是非常妙。代码如下：

#include<iostream>
#include<algorithm>

using namespace std;

string a, b;
int n, f[5009][5009];

int main() {
    cin >> n >> a;
    b = a;
    reverse(a.begin(), a.end());
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1]) {
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    cout << n - f[n][n];
}