POJ 1159

注意这个的最长公共子序列算法的空间复杂度

#include <stdio.h>
#include <string.h>
typedef unsigned int uint;
uint max(uint a,uint b){
  return a>b?a:b;
}
uint LCS(char* a,char*b){
  static uint matrix[2][5*1024]={{0},{0}};
  int i,j,k;
  for(i=0;a[i];++i) matrix[0][i]=0;
  for(i=1;a[i-1];++i){
      k=i%2;
      for(j=1;b[j-1];++j){
          if(a[i-1]==b[j-1])
              matrix[k][j]=matrix[!k][j-1]+1;
          else
              matrix[k][j]=max(matrix[k][j-1],matrix[!k][j]);
      }
  }
  return matrix[k][j-1];
}
int main() {
  char str[5001],s[5001];
  for(int n;scanf("%d%s",&n,str)+1;){
      strcpy(s,str);
      printf("%d\n",n-LCS(s,strrev(str)));
  }
  return 0;
}