曲师大2023大一新生排位赛-C.String题解

C.String

题目描述

众所周知，许师哥精通字符串。
一天，许师哥意外的获得了一个字符串，但他发现这个字符串并不是一个回文串，因此他非常生气。于是他决定从这个字符串中删除若干个字符使得 剩余的字符串为一个回文串。
回想回文串的定义：如果一个字符串正着读和反着读都是一样的字符串，那么这个字符串就是回文串。

输入描述

第一行有一个正整数 ，表示字符串的长度。
第二行有一个长度为 n 仅含有小写字母的字符串 s。

输出描述

输出一个整数，表示使得剩余字符串为回文串最少删除的字符数量。

样例

输入：

6
aabcaa

输出：

1

输入：

10
asdbdbdadb

输出：

3

思路：

这个题算是一个板子题，最长公共子序列问题。闫氏dp分析方法可以分析如下：

 对于这个题，我要找的是回文字符串，转化为我找字符串的正序和逆序的最长公共子序列问题

代码：

#include<bits/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];
}