1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<cstring>
using namespace std;
int n,f[2][5005];
char s1[5005],s2[5005];
int _max(int x,int y,int z)
{
  int tem=x;
  if (tem<y) tem=y;
  if (tem<z) tem=z;
  return tem;
}
int main()
{
  scanf("%d",&n); char ch=getchar();
  for (int i=1;i<=n;i++) s1[i]=getchar();
  for (int i=1;i<=n;i++) s2[i]=s1[n-i+1];
  memset(f,0,sizeof(f));
  for (int i=1;i<=n;i++)
  {
    memset(f[i&1],0,sizeof(f[i&1]));
    for (int j=1;j<=n;j++)
      f[i&1][j]=_max(f[1-(i&1)][j],f[i&1][j-1],f[1-(i&1)][j-1]+(s1[i]==s2[j]));
  }
  printf("%d",n-f[n&1][n]);
  return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX