POJ 1631 - Bridging signals（DP）

題目連結 https://cn.vjudge.net/problem/POJ-1631

【題意】

求最長上升子序列LIS

【輸入格式】

輸入整數T，共有T組輸入資料，每組輸入n（n <= 40000）代表序列長度，随後n個整數代表序列的内容。

【輸出格式】

輸出最長上升子序列的長度。

【思路】

LIS問題，注意利用二分O(nlogn)的算法求解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int inf=;
const int maxn=;

int n;
int a[maxn];
int dp[maxn];

int main(){
    cin.tie();
    ios_base::sync_with_stdio();
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=;i<n;++i) cin>>a[i];

        fill(dp,dp+maxn,inf);
        int len=-;
        for(int i=;i<n;++i){
            int pos=lower_bound(dp,dp+n,a[i])-dp;
            if(pos>len){
                ++len;
                dp[len]=a[i];
            }
            else dp[pos]=min(dp[pos],a[i]);
        }
        cout<<len+<<endl;
    }
    return ;
}