题解 P1435 【回文字串】

wisdom_grass · 2019-01-07 22:08:13 · 题解

我的思路跟楼下dalao的题解不太一样啊......

设字符串为S。

设f[i][j]为要把从i到j（包括i和j）的字符串变为回文串的最少插入字符数。

怎么转移？ 有两种可能：

• S[i] != s[j]$ 说明串的两头不同，需要多插入1字符以保持串的回文性质，我们这次新插入的字符可能在最右边，也可能在最左边。所以需要$f[i][j] = min(f[i+1][j], f[i][j-1]) + 1

具体初始化细节请看代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 1007;
int f[maxn][maxn];
char s[maxn];
int len; // 字符串长度

void dp() {
    for(int k = 1; k < len; k++) // 枚举头尾间距
        for(int i = 1; i <= len - k; i++) { // 枚举起点
            int j = i + k; // 算出终点
            if(s[i] == s[j]) {
                f[i][j] = f[i + 1][j - 1];
            } else {
                f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
            }
        }
}
int main() {
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    scanf("%s", s + 1); // 输入字符串，第一个字母在s[1]
    len = strlen(s + 1); // 从s[1]开始算字符串的长度

    //对于每一个只有一个字符的字符串来说，它必是回文
    for(int i = 1; i <= len; i++) f[i][i] = 0;
    dp();

    cout << f[1][len];
    return 0;
}

最后，我们可以向同学炫耀

我刷出了一道IOI题！