だんだん強く [第4回 ドワンゴからの挑戦状 本選 B]

https://beta.atcoder.jp/contests/dwacon2018-final-open/tasks/dwacon2018_final_b

前提知識

• インラインDP

解法

https://beta.atcoder.jp/contests/dwacon2018-final-open/submissions/2065434

最初に配列Vは大小関係だけが重要なので座圧できる。
座圧の時に番兵として-1を含んだ状態で座圧しておく。
　
これよりDPをする。
dp[idx][lastv][k] := idx日目までで、最後の放送日がlastvの音量で、k回ルール違反をしている時の放送の最大回数
遷移は、
dp[idx+1][V[idx]][k] = max{v=0..V[idx]-1} dp[idx][v][k] + 1
dp[idx+1][V[idx]][k] = max{v=V[idx]..max} dp[idx][v][k-1] + 1
となる。これには2つ重要なことがあり、「V[idx]しか更新処理が走らない」「区間minが分かれば高速に更新可能」
これよりインラインDPで解決していこう。

idxを省略した「dp[lastv][k] := 最後の放送日がlastvの音量で、k回ルール違反をしている時の放送の最大回数」をする。
この時DPは区間minのセグメントツリーで保持しておこう。
こうすることで更新を高速に行うことができる。
kは前回のk-1を使用するので後ろから更新する必要があることに注意。

int N, K, V[101010];
SegTree<int, 1 << 17> dp[105];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> V[i];
 
    vector<int> dic;
    dic.push_back(-1);
    rep(i, 0, N) dic.push_back(V[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
    rep(i, 0, N) V[i] = lower_bound(all(dic), V[i]) - dic.begin();
 
    dp[0].update(0, 0);
    rep(i, 0, N) rrep(k, K, 0) {
        int d = dp[k].get(0, V[i]);
        if (0 <= d) dp[k].update(V[i], max(dp[k][V[i]], d + 1));
 
        if (k) {
            d = dp[k - 1].get(V[i], 1 << 17);
            if (0 <= d) dp[k].update(V[i], max(dp[k][V[i]], d + 1));
        }
    }
 
    int ans = -1;
    rep(k, 0, K + 1) chmax(ans, dp[k].get(0, 1 << 17));
    cout << ans << endl;
}