tju/1006.c

   1 #include <stdio.h>
   2
   3 #define maxn 3010
   4
   5 int a[maxn],f[maxn][maxn]={0};
   6
   7 int min(int p, int q, int r) {
   8         p=(p<q?p:q);
   9         p=(p<r?p:r);
  10         return p;
  11 }
  12
  13 int query(int l, int r) {
  14         if (l>=r) return 0;
  15         if (f[l][r]) return f[l][r];
  16         if (a[l]==a[r]) return f[l][r]=query(l+1,r-1); else
  17                 return f[l][r]=min(query(l+1,r),query(l,r-1),query(l+1,r-1))+1;
  18 }
  19
  20 int main() {
  21         freopen("queue.in","r",stdin);
  22         freopen("queue.out","w",stdout);
  23         int n,i;
  24         scanf("%d",&n);
  25         for (i=1; i<=n; i++) scanf("%d",&(a[i]));
  26         printf("%d\n",query(1,n));
  27         return 0;
  28 }