TOI_10_PoF

#include<stdio.h>
int arr[1005][1005]={0},n,i,r,j,k;
char wrd[1005][2]={'\0'};
int main()
{
  scanf("%d",&n);
  for(i=1;i<=n;i++)
  {
    scanf("%s",&wrd[i]);
  }
  for(r=1;r<=n;r++)
  {
    for(i=1;i+r-1<=n;i++)
    {
      j=i+r-1;
      if(wrd[i][0]==wrd[j][0]&&i!=j)
      {
         if(arr[i+1][j-1]+1>arr[i][j])
         arr[i][j]=arr[i+1][j-1]+1;
      }
      else
      {
          for(k=i;k<j;k++)
      {
        if(arr[i][k]+arr[k+1][j]>arr[i][j])
        arr[i][j]=arr[i][k]+arr[k+1][j];
      }
      }
      //printf("%d %d %d\n",i,j,arr[i][j]);
    }
  }
  printf("%d",arr[1][n]);
return 0;
}