AtCoder ARC 006 C - 積み重ね (試験管緑色)

実は ABC 134 E とほとんど同じ！

• 問題へのリンク

問題概要

要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は広義単調減少になるようにしなければならない。

このようなことが可能となる色の種類数の最小値を求めよ。

制約

• 

考えたこと

次の問題とほとんど一緒である！！

drken1215.hatenablog.com

ただし、リンク先の問題を次のように変える

• (before) 各山の値が「狭義」単調「増加」
• (after) 各山の値が「広義」単調「減少」

解法はほとんど同じで、LIS に帰着できる。計算量は 。

#include <bits/stdc++.h>
using namespace std;

// dp[i] := 長さが i の増加部分列として最後尾の要素のとりうる最小値
template<class T> int LIS(vector<T> a,  bool is_strong = true) {
    const T INF = 1<<30; // to be set appropriately
    int n = (int)a.size();
    vector<T> dp(n, INF);
    for (int i = 0; i < n; ++i) {
        if (is_strong) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
        else *upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    cout << LIS(A) << endl;
}