题意：一个士兵列队，因为高度导致参差不齐，长官要求最少k个人出列，使得剩下的人在不改变相对次序的情况下，保证从左到右的高度保证严格满足 a1<a2<a3<...ai--ai+1>ai+2>ai+3>...>an。
上面这条表达式出来之后就很容易想到LIS了，也就是枚举ai和ai+1的位置，然后左半部分和又半部分分别往相反的方向做LIS，求出出列数最短的一个中点即可，其中做LIS可以采用二分查找，使得转移花费从O(n)降为O(lg n)。
1
#include<cstdio>
2#include<cstring>
3#define inf 0x7fffffff
4#define N 1001
5#define MAX(a,b) (a<b)?b:a
6#define MIN(a,b) (a<b)?a:b
7using namespace std;
8int lis[N],lds[N];
9double w[N];
10
11
int find(double c[],int len,double k)
{
12
int left=0,right=len,mid=(left+right)/2;
13
while(left<=right){
14 if( k>c[mid] ) left=mid+1;
15 else if( k<c[mid] ) right=mid-1;
16 else { return mid; }
17 mid=(left+right)/2;
18
}
19 return left;
20
}
21
22int main(){
23 int n,i,j,res;
24 int tmpDp[N];
25 double c[N];
26 while(scanf("%d",&n)!=EOF){
27 for(i=0;i<n;i++) scanf("%lf",&w[i]);
28
29 for(i=0;i<=n;i++) c[i]=inf;
30 c[0]=-1; c[1]=w[n-1];
31 memset(tmpDp,0,sizeof(tmpDp));
32 tmpDp[n-1]=1;
33 for(i=n-2;i>-1;--i){
34 j=find(c,n+1,w[i]);
35 c[j]=w[i]; tmpDp[i]=j;
36 }
37 for(j=-1,i=n-1;i>-1;--i){ j=MAX(j,tmpDp[i]); lds[i]=j; }
38
39 for(i=0;i<=n;i++) c[i]=inf;
40 c[0]=-1; c[1]=w[0];
41 memset(tmpDp,0,sizeof(tmpDp));
42 tmpDp[0]=1;
43 for(i=1;i<n;++i){
44 j=find(c,n+1,w[i]);
45 c[j]=w[i]; tmpDp[i]=j;
46 }
47 for(j=-1,i=0;i<n;++i){ j=MAX(j,tmpDp[i]); lis[i]=j; }
48
49 res=inf;
50 for(i=0;i<n;++i){
51 res=MIN(res,n-(lis[i]+lds[i+1]));
52 }
53 printf("%d\n",res);
54 }
55 return 0;
56}