1513 palindrome.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1513 Palindrome
Time Limit : 2000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
//先求出倒置的字符串和原本的字符串的LCS,再是总长度－LCS的长度
#include <iostream>
#include <string>
using namespace std;

const int Max=5001;

int main()
{
    int t,n,i,j;
    char a[Max],b[Max];
    int lcs[2][Max],pre,next;

    while(cin>>n)
    {
        cin>>a;
        for(i=0,j=n-1 ; i<n ; i++,j--)
            b[i]=a[j];
        b[n]='\0';
        memset(lcs,0,sizeof(lcs));
        next=1;pre=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(a[i]==b[j])
                    lcs[next][j+1]=lcs[pre][j]+1;
                else
                {
                    if(lcs[pre][j+1]>=lcs[next][j])
                        lcs[next][j+1]=lcs[pre][j+1];
                    else
                        lcs[next][j+1]=lcs[next][j];
                }
            }
            t=pre;
            pre=next;
            next=t;
        }
        cout<<n-lcs[pre][n]<<endl;
    }
    return 0;
}