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; }
补充:软件开发 , C++ ,