poj 1159 Palindrome(最长回文子串)

1、http://poj.org/problem?id=1159

2、题目大意：给出一个字符串，要求插入最少的字符，使得原字符串为一个回文串

看了别人的思路才懂，http://chjzhacm.blog.163.com/blog/static/1749014132011613105450310/

转换成最长公共子序列后还超内存，需要用滚动数组，参考百度文库滚动数组http://wenku.baidu.com/view/3af4a690daef5ef7ba0d3c0e.html

思路：

在这里，我们的思路似乎被卡住了，找不到状态表示

然而我们换个角度想

设S‘为原串S插入最少个字符所构成的回文串 令 X = S' – S

又原来的S我们可以划分成两个集合A跟B

A：{t|t在S‘中对称位置的元素也在S中}

B：{t|t在S‘中对称位置的元素不再S中}

例如：题目中所给的 S=Ab3bd

S‘ Adb3bdA

S A--b3bd--

则有A = {b,3,b} B ={d,A} X={d,A}

显然 |A| + |B| = |S| ------1'

|X| = |B| ------2'

联立1‘，2’可得：

|X| = |S| - |A|

要是|X|最小 则 |A|最大

到此，问题转化成求S的最大子回文串

设字符串S2由字符串S翻转而来，则S跟S2的最长公共子序列就

是S的最大子回文串(翻转前与翻转后相等&&最大)

所以问题最本质的就是求S与S2的最长公共子序列

F[i][j] = F[i-1][j-1] + 1 (S[i] == S2[j])

max(F[i-1][j],F[i][j-1]) (S[i]!=S2[j])

0 (i==0|j==0)

注意：maxn=5000 显然用二维数组空间会爆掉

可以用一个滚动数组来优化，把空间降到O(n)

ac代码：

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;int main()
{int n;string stra;int dpa[5005],dpb[5005],*now,*pre;while(cin>>n>>stra){string strb(stra);//拷贝字符串reverse(strb.begin(),strb.end());//可以直接翻转字符串memset(dpa,0,sizeof(dpa));memset(dpb,0,sizeof(dpb));now=dpa;pre=dpb;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(stra[i-1]==strb[j-1])now[j]=pre[j-1]+1;else{now[j]=max(now[j-1],pre[j]);}}int *temp;temp=now;now=pre;pre=temp;}cout<<n-pre[n]<<endl;}return 0;
}
/*
5
Ab3bd
*/

runtime erro代码：

#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{int n,dp[5005][5005];string stra;while(cin>>n>>stra){string strb(stra);reverse(strb.begin(),strb.end());for(int i=0;i<=n;i++){dp[1][i]=0;}dp[0][0]=0;int mx=-1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(stra[i-1]==strb[j-1])dp[i%2][j]=dp[(i-1)%2][j-1]+1;elsedp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);if(dp[i%2][j]>mx)mx=dp[i%2][j];}}cout<<n-mx<<endl;}return 0;
}