P1435 [IOI2000] 回文字串

youyong1 / 2024-10-23 / 原文

尝试了几次发现添加的字符数等于n-正着的和反着的最长公共子序列的长度，即为答案。正序与倒序“公共”的部分就是我们回文的部分，如果把正序与倒序公共的部分减去你就会惊奇的发现剩余的字符就是你所要添加的字符，也就是所求的正解。

点击查看代码

#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip> 
#define int long long 
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod  1000000007
#define N 1005
const double PI = 3.14159265358979323846;
using namespace std;
char s2[1005], s1[1005];
int dp[1005][1005];
signed main()
{
    ios;
    string s; cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        s1[i + 1] = s[i];
        s2[n - i] = s[i];
    }
    for (int i = 1; i <= n; i++)//s1
    {
        for (int j = 1; j <= n; j++)
        {
            if (s1[i] == s2[j])dp[i][j] = dp[i - 1][j - 1]+1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << n - dp[n][n] << endl;
    return 0;
}