Soxy Log

競技プログラミングに関すること

AtCoder ABC134 E - Sequence Decomposing

問題


AtCoder ABC134 E - Sequence Decomposing

解法


数列Aの広義単調減少列の長さの最大値が答えである。(解答)
A[N]からA[1]の順に走査し、最長の広義単調減少列dec_lenを求める。
A[i]>=dec_len[top]の場合、dec_lenにA[i]を追加し、topをインクリメントする。
そうでない場合、dec_len中のA[i]より大きい要素の最小値をA[i]で置き換える。
これを繰り返すことで、広義単調減少列の長さtopが求まる。

ソースコード

#include <bits/stdc++.h>
using namespace std;
int N, top, A[200001], dec_len[200001];
int main(){
    cin >> N;
    for(int i=N; i>=1; --i) cin >> A[i];
    for(int i=1; i<=N; ++i) {
        if(A[i]>=dec_len[top]){
            dec_len[++top]=A[i];
        }else {
            dec_len[upper_bound(dec_len+1,dec_len+top+1,A[i])-dec_len]=A[i];
        }
    }
    cout << top << endl;
    return 0;
}