这道题和以前NOI的一道名叫“合唱队形”的题目很相似，题目大意是给出一队士兵，要从中选一些人出来，使剩下的队列满足
a1 < a2 < a3 ... < a(i ) <=> a(i+1) > a(i+2) > .. a(n-1) > a(n)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <iostream>
using namespace std;
#define N 1001
double a[N];
int l[N] , r[N];
int main()
{
 int i,n,j,max = 0;
 cin>>n;
 for( i =0 ;i<n;i++)
  cin>>a[i];
 memset(l,0,sizeof(l));
 memset(r,0,sizeof(r));
 
 l[0] =1;
 for( i =1 ; i<n; i++)
 {
   l[i] =1;
   for(j = 0 ; j<i;j++)
   if(a[j]<a[i] && l[j] >=l[i])
    l[i] = l[j] + 1;
 }
 r[n-1] =1;
 for(i = n-2; i>=0;i--)
 {
   r[i] = 1;
   for( j =n-1;j>i;j--)
    if(a[i] > a[j] && r[i] <= r[j])
      r[i] = r[j] +1;
 }
 for(i=0;i<n-1;i++)
 for(j=i+1;j<n;j++)
  if(l[i] + r[j] >max)
  {
    max = l[i] + r[j];
  }
 cout<<n-max<<endl;
 return 0;
}

• Re:我的代码最简单 (8) liushuixingyun 2010-08-08 09:43:36