Algoogle

Algorithm for Programming Contest

PKU 1631 Bridging signals

Category: PKU Tag: dp

Bridging signals

問題概要


解法


交差する場合というのは入力の数列が単調増加ではないということなので
最長増加部分列を求めればよい

コード


(1631.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <iostream>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define INF 1e9
int q, n;
int path[40010], dp[40010];

int main(){
    cin >> q;
    while(q--){
        scanf("%d", &n);
        rep(i,n) scanf("%d", &path[i]);
        rep(i,n) dp[i] = INF;
        rep(i,n) *lower_bound(dp,dp+n,path[i]) = path[i];
        cout << lower_bound(dp,dp+n,INF) - dp << endl;
    }
    return 0;
}

Comments