本文主要是介绍【DP】回文词 （ssl 1813），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
回文词
ssl 1813
题目大意：
给出一个式子，最少要加多少个字符才能让这个式子是一个“回文词”
原题：
题目描述
回文词是一种对称的字符串,也就是说:一个回文词,从左向右读和从右向左读的结果都是一样的.任意给定一个字符串,通过插入若干个字符,都可以变成一个回文词.你的任务是写一个程序,求出给定字符串变成回文词所需插入的最小字符数.
比如,字符串"Ab3db",在插入两个字符后可以变成一个回文词(“dAb3bAd”,“Adb3bdA”),然而,插入两个以下的字符无法使它变成一个回文词.
输入
输入文件的第一行包含一个数Ｎ，表示给定字符串的长度（３<=N<=5000）
文件的第二行是一个长度为Ｎ的字符串。字符串仅由大写字母，小写字母，和数字构成。大写字母和小写字母被认为是不同的。
输出
输出只包括一行，包含一个整数，表示需要插入的字符数。
样例输入
５
Ａb3bd
样例输出
２
解题思路：
把式子倒着存一遍，然后和正着的做最长公共子序列，再用n减去结果
代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
int n,a[5005][5005];
char b[5005],c[5005];
string str;
int main()
{scanf("%d",&n);getchar();getline(cin,str);str=' '+str;for (int i=1;i<=n;++i){b[i]=str[i];c[i]=str[n-i+1];//反过来存}for (int i=1;i<=n;++i)for (int j=1;j<=n;++j){a[i&1][j]=max(a[i&1][j-1],a[(i+1)&1][j]);if (b[i]==c[j])//相同a[i&1][j]=max(a[i&1][j],a[(i+1)&1][j-1]+1);//滚动数组}printf("%d",n-a[n&1][n]);
}
这篇关于【DP】回文词 （ssl 1813）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
