poj 1631 Bridging signals (LIS 最长递增子序列 DP-二分) - c++编程基础

思路：LIS 最长递增子序列，如果用一般的动态规划算法，复杂度是O（n^2），题目的数据规模下会超时，采用二分的思想：复杂度是O（nlogn）

代码：

首先是一般的DP：

#include  
#include  
#include  
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>num[i];  
        memset(dp,0,sizeof(dp));  
        dp[0]=1;  
        for(int i=1;i

二分的代码：

#include  
#include  
#include  
#include  
#include  
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>num[i];  
        //vector dp;  
        int len=0;  
        //dp.push_back(num[0]);  
        dp[len++]=num[0];  
        for(int i=1;idp[len-1]) dp[len++]=num[i];  
            else{  
                int *pt=lower_bound(dp,dp+len,num[i]);  
                *pt=num[i];  
            }  
        }  
        cout<