POJ 1159 - Palindrome 优化空间LCS

时间:2023-03-10 01:49:13
POJ 1159 - Palindrome 优化空间LCS

将原串和其逆序串的最长公共子序列求出来为M..那么2*n-M就是所需要加的最少字符..因为求出的M就是指的原串中"潜伏"的最长回文..

问题转化为求LCS..但是n最大到5000...裸的LCS需要dp[5000][5000]..显然会爆空间.

.而更新的时候之于上一层的数据有关...所以空间不需要开5000*5000...滚动数组..只需2*5000就好...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<algorithm>
#include<cmath>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 10005
using namespace std;
int n,dp[2][5005];
char s1[MAXN],s2[MAXN];
int main()
{
//freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
int i,j,k;
while (~scanf("%d",&n))
{
scanf("%s",s1+1);
for (i=1;i<=n;i++) s2[i]=s1[n-i+1];
k=0;
for (i=1;i<=n;i++)
{
k=1-k;
for (j=1;j<=n;j++)
if (s1[i]==s2[j])
dp[k][j]=max(max(dp[1-k][j-1]+1,dp[1-k][j]),dp[k][j-1]);
else
dp[k][j]=max(dp[k][j-1],dp[1-k][j]);
}
printf("%d\n",n-dp[k][n]);
}
return 0;
}