リンゴの出荷 / Apples [JOI2018 予選模試 E]

https://www.hackerrank.com/contests/joi2018/challenges/apples-5

前提知識

• 動的計画法

解説

最大値で個数制限があり、10^3制約ということなので、dp[10^3][10^3]っぽさがある。
ここから考えると、
dp[i][m] := i番目までのりんごをm箱に詰めたときの美しさの総和の最大値
状態数が10^6くらいあるので、遷移は頑張る必要がある。
遷移先は普通にやると、O(N)通りあるが、ここで遷移を貪欲法を使って減らそう。
　
まず重要な性質が「りんごを多く詰めて、美しさが下がることは無い」ということ。
つまり、最大値と最小値が同じであれば、なるべく少ない個数で詰めて、
後に詰めるりんごを残しておく戦略が有効であるということ。
よって、遷移先は「最大値と最小値が変わる境界線だけ見ればいい」ということになる。
　
その境界線を高速に見つけ出す方法だが、これはnxt配列を使おう。
nxt[i][a] := i番目のりんごより後のりんごで濃さがaであるりんごは最も近い所で何番目か
これは累積minを使えば高速に計算できる。
こうすると、i+1番目のりんごを左端として、箱に詰めるりんごを考えると、
nxt[i][1], nxt[i][2], ... , nxt[i][6]が右端の候補になる。
これをソートすると、右端を順番に伸ばしたときに、最大値最小値の変化を見ることができる。
これで遷移を行う。
　
答えは、毎回、右端を一番端まで伸ばしたときの美しさの総和の最大値を取っていく。

int N, M, A[1010];
int dp[1010][1010];
int nxt[1010][6];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N + 1) rep(a, 0, 6) nxt[i][a] = inf;
    rep(i, 0, N) nxt[i][A[i]] = i + 1;
    rep(a, 1, 6) rrep(i, N - 1, 0) chmin(nxt[i][a], nxt[i + 1][a]);

    rep(i, 0, N + 1) rep(m, 0, M + 1) dp[i][m] = -1;
    dp[0][0] = 0;

    int ans = 0;
    rep(i, 0, N) rep(m, 0, M) if(0 <= dp[i][m]) {
        vector<pair<int, int>> v;
        
        rep(a, 1, 6) v.push_back({ nxt[i][a], a });
        sort(all(v));

        int mi = 10, ma = -1;
        fore(p, v) {
            if (p.first == inf) break;
            chmin(mi, p.second);
            chmax(ma, p.second);
            chmax(dp[p.first][m + 1], dp[i][m] + ma - mi);
        }
        chmax(ans, dp[i][m] + ma - mi);
    }
    cout << ans << endl;
}