大致题意：给出一队士兵的身高，一开始不是按身高排序的。要求最少的人出列，使原序列的士兵的身高先递增后递减。
求递增和递减不难想到递增子序列，要求最少的人出列，也就是原队列的人要最多。
1 2 3 4 5 4 3 2 1
这个序列从左至右看前半部分是递增，从右至左看前半部分也是递增。所以我们先把从左只右和从右至左的LIS分别求出来。
如果结果是这样的：
A[i]={1.86 1.86 1.30621 2 1.4 1 1.97 2.2} //原队列
a[i]={1 1 1 2 2 1 3 4}
b[i]={3 3 2 3 2 1 1 1}
如果是A[1]~A[i]递增，A[i+1]~A[8]递减。此时就是求：a[1]~a[i]之间的一个值与b[i+1]~b[8]之间的一个值的和的最大值。
O(n^2)和O(nlogn)算法都可以过。
O(n^2)算法：
#include <iostream>
#include <cstdio>
using namespace std; const int Max=1e3+; int main()
{
//freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
double a[Max]={};
for(int i=; i<n; i++)
scanf("%f",a+i);
int l[Max]= {},r[Max]= {};
l[]=r[n-]=;
for(int i = ; i < n; i++)
{
int maxLen = ;
for(int j = ; j < i; j++)
if(a[j]<a[i])
maxLen = max(maxLen,l[j]);
l[i] = maxLen + ;
}
for(int i=n-; i>=; i--)
{
int maxLen=;
for(int j=n-; j>i; j--)
if(a[j]<a[i])
maxLen=max(maxLen,r[j]);
r[i]=maxLen+;
}
int maxlen=;
for(int i=;i<n-;i++)
for(int j=i+;j<n;j++)
maxlen=max(maxlen,l[i]+r[j]);
printf("%d\n",n-maxlen);
return ;
}
O(nlogn)算法
#include <iostream>
#include <cstdio>
using namespace std; const int Max=1e3+;
int l[Max]= {},r[Max]= {};
double B[Max];
int BinarySearch(double *a, double value, int n)
{
int low = ;
int high = n - ;
while(low <= high)
{
int mid = (high + low) / ;
if(a[mid] == value)
return mid;
else if(value<a[mid])
high = mid - ;
else
low = mid + ;
}
return low;
}
int LIS_DP_NlogN(double *a, int n,int *Len)
{
int nLISLen = ;
B[] = a[];
for(int i = ; i < n; i++)
{
if(a[i] > B[nLISLen - ])
{
B[nLISLen] = a[i];
nLISLen++;
Len[i]=nLISLen;
}
else
{
int pos = BinarySearch(B, a[i], nLISLen);
B[pos] = a[i];
Len[i]=pos+;
}
}
return nLISLen;
}
int main()
{
//freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
double a[Max]={};
double b[Max]={};
l[]=r[]=;
for(int i=; i<n; i++)
{
scanf("%f",a+i);
b[n-i-]=a[i];
}
LIS_DP_NlogN(a,n,l);
LIS_DP_NlogN(b,n,r);
int maxlen=;
for(int i=;i<n-;i++)
for(int j=n-i-;j>=;j--)
maxlen=max(maxlen,l[i]+r[j]);
printf("%d\n",n-maxlen);
return ;
}