AT4825 [ABC134E] Sequence Decomposing

原题链接

• 题意：如果 (A_i) 和 (A_j) 同色，那么必须满足 (i < j) 并且 (A_i < A_j)，求最小的颜色来涂满整个序列。
• 题解：很显然的是，要求最长不上升子序列，然后因为只能求最长上升子序列，和最长不下降子序列，然后又已知结论最长不上升子序列又是可以转化为，原序列相反的最长不下降子序列。然后还要注意一点就是相等时要用 (upper_bound) 函数。
• 代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;
const ll NN = 1e7 + 99;
const ll N = 2e6 + 99;
const ll mod = 1e9 + 7;

const ll maxn = 1e7;
ll stk[N];
ll fac[N];
ll inv_fac[N];
ll q_pow(ll a, ll k) {
    ll ret = 1;
    ll x = a;
    while (k) {
        if (k & 1) (ret *= x) %= mod;
        k >>= 1;
        (x *= x) %= mod;
    }
    return ret;
}

ll inv(ll a) { return (q_pow(a, mod - 2) % mod + mod) % mod; }
void init() {
    fac[0] = 1;
    inv_fac[0] = 1;
    fac[1] = 1;
    for (ll i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv_fac[i] = inv(fac[i]);
    }
}

ll C(ll n, ll m) { return fac[n] * inv_fac[m] % mod * inv_fac[n - m] % mod; }
ll dp[N];
ll a[N];
ll len;
ll ans[N];
void solve() {
    ll n, m;cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
    }
    reverse(a +1,a + 1 + n);
    dp[++len] = a[1];
    ans[1] = len;
    for (int i = 2; i <= n; i ++) {
        if (a[i] >= dp[len]) {
            dp[++len] = a[i];
            ans[i] = len;
        }
        else {
            ll pos = upper_bound(dp + 1, dp + 1 + len, a[i]) - dp;
            dp[pos] = a[i];
            ans[i] = pos;
        }
    }
    cout << len << endl;
    for (int i = n; i >= 1; i --) {
        if (ans[i] == len) {
            len--;
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    init();
    ll t = 1;
    while (t--) solve();
    return 0;
}