hdu1513(最长公共子序列)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 10010
using namespace std;
char s1[5110],s2[5110];
int dp[2][5110];
int main()
{
    int n;
    while(scanf("%d",&n)>0)
    {
        scanf("%s",s1);
        for(int i=1; i<=n; i++)
        {
            s2[i-1]=s1[n-i];
        }
        memset(dp,0,sizeof(dp));
        int cur=0,nxt=1;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(s1[i-1]==s2[j-1])
                    dp[nxt][j]=dp[cur][j-1]+1;
                else
                    dp[nxt][j]=max(dp[nxt][j-1],dp[cur][j]);
            }
            swap(cur,nxt);
        }
        printf("%d\n",n-dp[cur][n]);
    }
}