程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1631 Bridging signals (LIS 最長遞增子序列 DP-二分)

poj 1631 Bridging signals (LIS 最長遞增子序列 DP-二分)

編輯:C++入門知識

思路:LIS 最長遞增子序列,如果用一般的動態規劃算法,復雜度是O(n^2),題目的數據規模下會超時,采用二分的思想:復雜度是O(nlogn) 代碼: 首先是一般的DP:   

#include<iostream>  
#include<cstring>  
#include<cstdlib>  
using namespace std;  
const int MAX=40001;  
int dp[MAX],num[MAX];  
int main()  
{  
    int T;  
    cin>>T;  
    while(T--){  
        int p;  
        cin>>p;  
        for(int i=0;i<p;i++) cin>>num[i];  
        memset(dp,0,sizeof(dp));  
        dp[0]=1;  
        for(int i=1;i<p;i++){  
            int res=0;  
            for(int j=0;j<i;j++){  
                if(num[j]<num[i]) res=max(res,dp[j]);  
            }  
            dp[i]=res+1;  
        }  
        int res=0;  
        for(int i=0;i<p;i++) res=max(res,dp[i]);  
        cout<<res<<endl;  
    }  
    return 0;  
}  

 

    二分的代碼:  
#include<iostream>  
#include<cstring>  
#include<vector>  
#include<algorithm>  
#include<cstdlib>  
using namespace std;  
const int MAX=40001;  
int num[MAX],dp[MAX];  
int main()  
{  
    int T;  
    cin>>T;  
    while(T--){  
        int p;  
        cin>>p;  
        for(int i=0;i<p;i++) cin>>num[i];  
        //vector<int> dp;  
        int len=0;  
        //dp.push_back(num[0]);  
        dp[len++]=num[0];  
        for(int i=1;i<p;i++){  
            if(num[i]>dp[len-1]) dp[len++]=num[i];  
            else{  
                int *pt=lower_bound(dp,dp+len,num[i]);  
                *pt=num[i];  
            }  
        }  
        cout<<len<<endl;  
    }  
    return 0;  
}  

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved