当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,