POJ1836——DP（LCS+LDS）——Alignment

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1100;
double a[MAX];
double b[MAX],c[MAX];
double k1[MAX],k2[MAX];
int main()
{
    int n, l, r, mid;
    scanf("%d",&n);
    for(int i = 1; i <= n;i++)
        scanf("%lf",&a[i]);
    int t1 ,t2 ;
    int max1 = 0;
    int p;
    for( p = 0; p <= n;p++){
            memset(b,0,sizeof(b));
            memset(c,0,sizeof(c));
            t1 = t2 = 1;
        if( p == 0){
                for(int j = 1; j <= n;j++)
                 c[t2++] = a[j];
        }
        else if(p == n){
                for(int j = 1; j <= n ;j++)
                b[t1++] = a[j];
        }
        else {
          for(int j = 1; j <= p ;j++)
            b[t1++] = a[j];
          for(int j = p + 1 ; j <= n ;j++)
            c[t2++] = a[j];
        }

          //LCS
         k1[1] = b[1];
         int i, k;
         for(i = 2, k = 1; i < t1; i++){
              if(b[i] > k1[k]) k1[++k] = b[i];
         else {
             l = 1, r = k;
            while( l <= r){
                mid = (l + r) /2;
               if(k1[mid] < b[i]) l = mid + 1;
               else if(k1[mid] > b[i]) r = mid - 1;
               else break;
            }
            k1[l] = a[i];
           }
         }
         if(p == 0) k = 0;
         int temp1 = k;
         //LDS
     //    for(int q = 1; q < t2; q++)
       //     printf("%.2lf ",c[q]);
         k2[1] =c[1];
         for(i = 2, k = 1; i < t2; i++){
             if(c[i] < k2[k]) k2[++k] = c[i];
         else {
            l = 1, r = k;
         while( l <= r){
               mid = (l + r) /2;
              if(k2[mid] > c[i]) l = mid + 1;
              else if(k2[mid] < c[i]) r= mid - 1;
              else break;
         }
         k2[l] = c[i];
           }
         }
         if(p == n) k = 0;
         int temp2 = k;
        int x = temp1 + temp2;
       // printf("%d %d\n",temp1,temp2);

        max1 = max(max1,x);
    }
    printf("%d",n - max1);
   return 0;
}