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

問題
解法
解答

問題

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

解法

以下の DP を考える．

dp(i, j) := i 日目で右側に j 枚コインがあるとき，i + 1 日目以降のコストの和の最小値

遷移は，右側にのせるコインは j 枚のまま次の日にいくか，右側にのせるコインを 1 枚増やすかの 2 通りになる．dp(i, j) = min( dp(i + 1, j) + std::abs(M[i][j] - (M[i][N] - M[i][j])), dp(i, j + 1) ) とすればよい．1 ~ k 枚目までのコインの重さの総和を O(1) で得られるようにするため，前処理で累積和を各日ごとにとっておく．O(ND)．