Palindrome
Time Limit:3000MSMemory Limit:65536K
Total Submissions:56150Accepted:19398
Description
A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
Input
Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from ‘A’ to ‘Z’, lowercase letters from ‘a’ to ‘z’ and digits from ‘0’ to ‘9’. Uppercase and lowercase letters are to be considered distinct.
Output
Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.
Sample Input
5Ab3bd
Sample Output
2
给一个字符串，计算最少加多少个字符能够使字符串变成回文串（即从前往后读与从后往前读一样）。
有2种思路，一种是直接区间DP，dp[j][i]表示[i,j]这个子串要变成回文串需要添加多少个字符，状态转移方程如下：if(s[i]==s[j]) dp[j][i]=dp[j+1][i-1];else dp[j][i]=1+min(min[j+1][i],min[j][i-1])第二种思路也比较容易想，要将一个字符串变为回文串，那么我们就可以先得到这个字符串的逆序串，然后再求出这两个的最长公共子序列，要添加的字符数就是字符串长度减去最长公共子序列的长度。
另外，这道题还会限制内存。如果定义一个5000*5000的数组会Memory Limit Exceeded。有两种解决方案，一是把数组定义成short型，这样原本的内存会减少很大一部分，大概会在50000kb左右，刚好能够AC；另一种解决方案：因为计算第i行时只需要知道第i-1行，所以可以开一个2*5000的滚动dp数组，，这种方法比较推荐，非常节省内存。
/*LCS+shortMemory: 49688 KBTime: 1094 MSLanguage: G++Result: Accepted*/#include<stack>#include<queue>#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#pragma commment(linker,"/STACK: 102400000 102400000")#define lson a,b,l,mid,cur<<1#define rson a,b,mid+1,r,cur<<1|1using namespace std;const double eps=1e-6;const int MAXN=5001;char s[MAXN],t[MAXN];int n,ans,tlen;short int dp[MAXN][MAXN];int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEwhile(scanf("%d",&n)!=EOF){scanf("%s",s+1);for(int i=n;i>=1;i–)t[n-i+1]=s[i];t[n+1]=0;memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(s[i]==t[j])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);printf("%d\n",n-dp[n][n]);}return 0;}/*DP+shortMemory: 55716 KBTime: 1454 MSLanguage: G++Result: Accepted*/#include<stack>#include<queue>#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#pragma commment(linker,"/STACK: 102400000 102400000")#define lson a,b,l,mid,cur<<1#define rson a,b,mid+1,r,cur<<1|1using namespace std;const double eps=1e-6;const int MAXN=5300;char s[MAXN];short int n,dp[MAXN][MAXN];int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEwhile(scanf("%d",&n)!=EOF){scanf("%s",s);memset(dp,0,sizeof(dp));for(int i=1;i<n;i++)for(int j=i-1;j>=0;j–){if(s[i]==s[j])dp[j][i]=dp[j+1][i-1];elsedp[j][i]=(short int)(min(dp[j+1][i],dp[j][i-1])+1);}printf("%d\n",dp[0][n-1]);}return 0;}/*LCS+滚动数组Memory: 728 KBTime: 735 MSLanguage: G++Result: Accepted*/#include<stack>#include<queue>#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#pragma commment(linker,"/STACK: 102400000 102400000")#define lson a,b,l,mid,cur<<1#define rson a,b,mid+1,r,cur<<1|1using namespace std;const double eps=1e-6;const int MAXN=5001;char s[MAXN],t[MAXN];int n,ans,tlen,dp[2][MAXN];int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEwhile(scanf("%d",&n)!=EOF){scanf("%s",s+1);for(int i=n; i>=1; i–)t[n-i+1]=s[i];t[n+1]=0;memset(dp,0,sizeof(dp));int indexs=0;for(int i=1; i<=n; i++){indexs=!indexs;for(int j=1; j<=n; j++)if(s[i]==t[j])dp[indexs][j]=dp[!indexs][j-1]+1;elsedp[indexs][j]=max(dp[!indexs][j],dp[indexs][j-1]);}printf("%d\n",n-dp[indexs][n]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
后来逐渐有广州花城的，
