题意：n个士兵站成一排，求去掉最少的人数，使剩下的这排士兵的身高形成“峰形”分布，即求前面部分的LIS加上后面部分的LDS的最大值。
做法：分别求出LIS和LDS，枚举中点，求LIS+LDS的最大值。。
注意一点，有可能最中间的值重复，也有可能不重复，所以要考虑这两种情况：（假设中点为K）
1）不重复的情况，求LIS(K) + LDS(K+1)的最大值
2）重复的情况，这时K既包含在LIS当中，也包含在LDS中，计算了两次，最终结果要减掉1
复杂度：O(n^2)
代码：
#include <iostream>
#include <cstdio>
using namespace std;
#define N 1007 int dpi[N],dpd[N]; //LIS和LDS
double a[N]; int main()
{
int n,i,j,k,maxi,mm;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<n;i++)
scanf("%lf",&a[i]);
for(i=;i<n;i++)
dpi[i] = ,dpd[i] = ;
for(i=;i<n;i++)
{
maxi = -;
for(j=;j<i;j++)
{
if(a[j] < a[i])
{
if(dpi[j] > maxi)
maxi = dpi[j];
}
}
dpi[i] = max(dpi[i],maxi+);
}
for(i=n-;i>=;i--)
{
maxi = -;
for(j=n-;j>i;j--)
{
if(a[j] < a[i])
{
if(dpd[j] > maxi)
maxi = dpd[j];
}
}
dpd[i] = max(dpd[i],maxi+);
}
int k1,k2;
int res = -;
for(k=;k<=n-;k++) //中点重复的情况
{
mm = -;
for(i=;i<=k;i++)
{
if(dpi[i] > mm)
mm = dpi[i];
}
k1 = mm;
mm = -;
for(i=n-;i>=k;i--)
{
if(dpd[i] > mm)
mm = dpd[i];
}
k2 = mm;
res = max(res,k1+k2-);
}
for(i=;i<n;i++) //中点不重复的情况
{
for(j=i+;j<n;j++)
{
if(dpi[i]+dpd[j] > res)
res = dpi[i]+dpd[j];
}
}
printf("%d\n",n-res);
}
return ;
}