题意:一个字符串要变成回文串至少要插入多少个字符
分析:LCS,长度 - 原串和反串的最大相同长度就是要插入的个数。解释一下,当和反串相同时,在原串中已经是回文的部分了,那么减去LCS长度后剩下的多少个插入多少个一定就能使原串回文dp数组二维都开5000的话就会超内存,这里就用到了滚动数组,因为在LCS的计算中,i的变化只相差1,所以可以通过对2取余来进行滚动:)
收获:原串和反串取LCS能得到部分回文串,推荐继续看:UVA 11404 Palindromic Subsequence
代码:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std; const int MAXN = 5e3 + 10;
const int INF = 0x3f3f3f3f;
int dp[2][MAXN];
string s, ss; int LCS(int n) {
int x = 0;
for (int i=1; i<=n; ++i) {
x = 1 - x;
for (int j=1; j<=n; ++j) {
if (ss[i-1] == s[j-1]) {
dp[x][j] = dp[1-x][j-1] + 1;
}
else {
dp[x][j] = max (dp[x][j-1], dp[1-x][j]);
}
}
} return dp[x][n];
} int main(void) {
int n;
while (~scanf ("%d", &n)) {
memset (dp, 0, sizeof (dp));
cin >> ss;
s = ss;
reverse (s.begin (), s.end ()); int res = LCS (n);
printf ("%d\n", n - res);
} return 0;
}