LCS(滚动数组) POJ 1159 Palindrome

时间:2021-10-02 04:37:34

题目传送门

题意:一个字符串要变成回文串至少要插入多少个字符

分析: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;
}