poj 1159 Palindrome

Description

Input

Output

Sample Input

5
Ab3bd

Sample Output

2

需要加的字符的个数=原来字符串的长度-原来字符串和逆字符串的最长公共子序列的长度。

用滚动数组或用short int防止超内存。

#include"stdio.h"
#include"string.h"
#define mmax(a,b) (a>b?a:b)
#define N 5005
short  dp[2][N];
int main()
{
    int i,j,n;
    char str[N],s[N];
    while(scanf("%d",&n)!=-1)
    {
        scanf("%s",str);
        for(i=0;i<n;i++)
        {
            s[i]=str[n-1-i];
        }
        s[n]='\0';
        memset(dp,0,sizeof(dp));
        int ans=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(str[i]==s[j])
                {
                    dp[(i+1)%2][j+1]=dp[i%2][j]+1;
                }
                else
                {
                    dp[(i+1)%2][j+1]=mmax(dp[(i+1)%2][j],dp[i%2][j+1]);
                }
                ans=mmax(ans,dp[(i+1)%2][j+1]);
            }
        }
        printf("%d\n",n-ans);
    }
    return 0;
}

poj 1159 Palindrome,布布扣,bubuko.com

poj 1159 Palindrome

原文：http://blog.csdn.net/u011721440/article/details/26381785