洛谷 P1435 回文字串

题目传送门

解题思路:

就是求一个字符串的最长回文子序列的长度,然后用整个的长度减去最长回文子序列的长度

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<map>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 string l1,l;
 9 int len,c[1001],tot,f[1001][1001],ll;
10 map<char,int> a;
11 
12 int main() {
13     cin >> l;
14     l1 = l;
15     int len = l.length();
16     ll = len;
17     for(int i = 0;i < len; i++)
18         l1[--ll] = l[i];
19     for(int i = 0;i < len; i++)
20         for(int j = 0;j < len; j++)
21             f[i][j] = max(f[i-1][j],max(f[i][j-1],f[i-1][j-1] + (l[i] == l1[j])));
22     printf("%d",len - f[len-1][len-1]); 
23     return 0;
24 }