Source Code

Problem: 1159  User: yzhw 
Memory: 440K  Time: 594MS 
Language: GCC  Result: Accepted 

Source Code 
# include <stdio.h>
int min(int a,int b)
{
    return a<b?a:b;
}
char str[6000];
int refer[3][5010];
int n;
int main()
{
    int i,j;
    scanf("%d %s",&n,str+1);
    for(i=1;i<=n;i++)
      refer[0][i]=0;
    for(i=1;i<n;i++)
      refer[1][i]=(str[i]==str[i+1]?0:1);
    for(i=3;i<=n;i++)
    {
       for(j=1;j<=n-i+1;j++)
       {
           if(str[j]==str[j+i-1])
              refer[(i-1)%3][j]=refer[(i-3)%3][j+1];
           else
               refer[(i-1)%3][j]=min(refer[(i-2)%3][j],refer[(i-2)%3][j+1])+1;
           //printf("%d %d %d\n",j,j+i-1,refer[j][j+i-1]);
       }
    }
    printf("%d\n",refer[(n-1)%3][1]);
   // system("pause");
    return 0;
}