poj 1836 士兵战队 动态规划
思路：
找最长上升的子序列和最长下降的子序列，状态式分别如下
LIS[i]=max{LIS[j]}+1 ，其中0<=j<i且A[j]<A[i] 从数组开始向结尾
LDS[i]=max{LDS[j]}+1，其中i<j<=n-1且A[j]<A[i] 从数组结尾向开始
然后找到中间的位置x ，使得从0到x的最长上升子序列尽可能大，x+1到数组末尾之间的下降子序列尽可能长（注：不一定从x+1开始哦，下降子序列的最长长度，我就栽在这里）
代码如下：
#include<iostream>using namespace std;const int MAX=1005;double height[MAX],f[MAX],d[MAX];int n;int main(){while(cin>>n && n){int i,j,max,maxd;for(i=0;i<n;i++)cin>>height[i];f[0]=1;d[n-1]=1;for(i=1;i<n;i++){max=0;for(j=0;j<i;j++){if(height[j]<height[i])max=(f[j]>max?f[j]:max);}f[i]=max+1;}for(i=n-2;i>=0;i--){maxd=0;for(j=n-1;j>i;j--){if(height[j]<height[i])maxd=(d[j]>maxd?d[j]:maxd);}d[i]=maxd+1;}int ans=0x80000000;int lis=0x80000000,lds;for(i=0;i<n;i++){lis=lis>f[i]?lis:f[i];lds=0x80000000;for(j=i+1;j<n;j++) //注意这里，得向后找，因为不是累加到每一位的最大值，中间有小的lds=lds>d[j]?lds:d[j];ans=ans>(lis+lds)?ans:(lis+lds);}cout<<n-ans<<endl;}return 0;}