• \(dp_{0, i, x}\)：\(B\) の \(i\) 番目までの部分列であるようなジグザグ列のうち、先頭が \(x\) であり先頭の \(1\) つ手前が \(x\) 未満であるようなものの長さの最大値
• \(dp_{1, i, x}\)：\(B\) の \(i\) 番目までの部分列であるようなジグザグ列のうち、先頭が \(x\) であり先頭の \(1\) つ手前が \(x\) より大きいようなものの長さの最大値

とする動的計画法を考えます。これは正しい答えを与えますが、そのまま実装すると状態数 \(O(N \max B_i)\) 、遷移 \(O(\max B_i)\) となり、実行時間制限に間に合わせることができません。

そこで、与えられた数列 \(B\) を座標圧縮することで状態数、遷移をそれぞれ \(O(N^2)\)、\(O(N)\) に改善できます。 また、セグメントツリーを用いて動的計画法の配列を in-place に更新することで、全体計算量 \(O(N \log N)\) でこの問題を解くことができます。

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
int op(int x, int y) { return max(x, y); }
int e() {return -(1 << 30); }
int main() {
    int n; cin >> n;
    vector<int> b(n);
    for (int i=0; i<n; i++) cin >> b[i];
    vector<int> c = b;
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    atcoder::segtree<int, op, e> dp0(n);
    atcoder::segtree<int, op, e> dp1(n);
    for (int i=0; i<n; i++) {
        int pos = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
        int mx = max(0, dp0.prod(pos+1, n));
        dp1.set(pos, max(dp1.get(pos), mx + 1));
        mx = max(0, dp1.prod(0, pos));
        dp0.set(pos, max(dp0.get(pos), mx + 1));
    }
    int ans = max(dp0.all_prod(), dp1.all_prod());
    cout << ans << '\n';
}