• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

poj 1836(动态规划最长正序子序列)

开发技术 开发技术 1天前 5次浏览
#include<iostream>
using namespace std;
const int maxn = 1005;
double data[maxn];
int f[maxn],g[maxn],n,ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>data[i];
            f[i] = 1;
            g[i] = 1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                if(data[j]<data[i]){
                    f[i] = max(f[i],f[j]+1);
                }
            }
        }
        for(int i=n;i>0;i--){
            for(int j=n;j>i;j--){
                if(data[j]<data[i]){
                    g[i] = max(g[i],g[j]+1);
                }
            }
        }
        ans = -1;
//        for(int i=1;i<=n;i++){
//            if((i>1&&data[i-1]==data[i])||(i<n&&data[i]==data[i+1])){
//                ans = max(ans,f[i]+g[i]);
//            }
//            else{
//                ans = max(ans,f[i]+g[i]-1);
//            }
//        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                ans = max(ans,f[i]+g[j]);
            }
        }
        cout<<n-ans<<endl;
    }
    return 0;
}

 


程序员灯塔
转载请注明原文链接:poj 1836(动态规划最长正序子序列)
喜欢 (0)