POJ 1159 LCS 黑书练习题

//使用short能过，使用int会超内存，公共个数总共也就5000，所以short是可行的 
#include<iostream>
using namespace std;
char x[5005];
char y[5005];
short c[5005][5005];
int len;
int i,j; 
int comlen;
void lcs(){
    for(i=1;i<=len;i++)
        c[i][0]=0;
    for(j=1;j<=len;j++)
        c[0][j]=0;
    for(i=1;i<=len;i++)
       for(j=1;j<=len;j++){
           if(x[i]==y[j])
               c[i][j]=c[i-1][j-1]+1;
           else if(c[i-1][j]>=c[i][j-1])
               c[i][j]=c[i-1][j];
           else
               c[i][j]=c[i][j-1]; 
       }
    comlen=c[len][len];
}
int main(){
    while(scanf("%d%s",&len,x+1)!=EOF){
        //将x逆序赋值给y 
        for(i=1;i<=len;i++){
            y[len-i+1]=x[i];
        }
        lcs();
        cout<<len-comlen<<endl;
    }
    return 0;
}