网站建设365,电子商务公司是干什么的,html5手机网站下载,中国能源建设集团有限公司是央企C.String
题目描述
众所周知#xff0c;许师哥精通字符串。 一天#xff0c;许师哥意外的获得了一个字符串#xff0c;但他发现这个字符串并不是一个回文串#xff0c;因此他非常生气。于是他决定从这个字符串中删除若干个字符使得 剩余的字符串为一个回文串。 回想回文串…C.String
题目描述
众所周知许师哥精通字符串。 一天许师哥意外的获得了一个字符串但他发现这个字符串并不是一个回文串因此他非常生气。于是他决定从这个字符串中删除若干个字符使得 剩余的字符串为一个回文串。 回想回文串的定义如果一个字符串正着读和反着读都是一样的字符串那么这个字符串就是回文串。
输入描述
第一行有一个正整数 表示字符串的长度。 第二行有一个长度为 n 仅含有小写字母的字符串 s。
输出描述
输出一个整数表示使得剩余字符串为回文串最少删除的字符数量。
样例 输入 6 aabcaa 输出 1 输入 10 asdbdbdadb 输出 3 思路
这个题算是一个板子题最长公共子序列问题。闫氏dp分析方法可以分析如下 对于这个题我要找的是回文字符串转化为我找字符串的正序和逆序的最长公共子序列问题
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
int f[2100][2100];
int main()
{int n;cin n;string s1,s2;cin s1;s2 s1;reverse(s2.begin(),s2.end());s1 s1;s2 s2;for(int i 1;i n;i){for(int j 1;j n;j){if(s1[i] ! s2[j]){f[i][j] max(f[i - 1][j],f[i][j - 1]);}else{f[i][j] f[i - 1][j - 1] 1;}}}cout n - f[n][n];
}
