天秤とコイン (Balance and Coins) [大手前プロコン 2019 F]

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_f

前提知識

• DP更新最適化

解説

https://atcoder.jp/contests/otemae2019/submissions/6931848

最小値を求める問題で制約も10³くらいなので、DPかフローかという雰囲気がある。
まずはDPから考えてみる。
10³制約でのDPはdp[10³][10³]が基本なので、これで考える。
dp[day][moved] := day日終わっていて、すでにmoved個コインを移動させたときの最小コスト
dp[10³][10³]では、遷移を工夫するしかないので、最適化する方針で考える。
まずは貰うDPで考える。

dp[day][moved]の更新を考える。
moved移動させた後のコストはmovedによって一定なので、それまでのコストの最小値が知りたくなる。
つまり、dp[day-1][0]～dp[day-1][moved]の最小値 + moved移動させた後のコストが更新値になる。
前半部分はは累積和を使って高速に求めよう。
後半部分は、M[i][j] = M[i][0] + M[i][1] + ... M[i][j]のように変換させて、累積和しよう。

int N, D;
ll M[2010][2010];
ll dp[2010][2010];
//---------------------------------------------------------------------------------------------------
ll get(int day, int moved) {
    ll tot = M[day - 1][N - 1];
    ll R = 0;
    if(0 < moved) R = M[day - 1][moved - 1];
    ll L = tot - R;

    return abs(R - L);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;
    rep(i, 0, D) rep(j, 0, N) cin >> M[i][j];
    rep(i, 0, D) rep(j, 1, N) M[i][j] += M[i][j - 1];

    rep(day, 0, D + 1) rep(moved, 0, N + 1) dp[day][moved] = infl;
    dp[0][0] = 0;

    rep(day, 1, D + 1) {
        ll mi = infl;
        rep(moved, 0, N + 1) {
            chmin(mi, dp[day - 1][moved]);
            chmin(dp[day][moved], mi + get(day, moved));
        }
    }

    ll ans = infl;
    rep(moved, 0, N + 1) chmin(ans, dp[D][moved]);
    cout << ans << endl;
}