人権なし

競プロで解いた問題や開発の進捗などの記録です

大手前プロコン 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).

解答

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

f:id:babcs2035:20190805155605p:plain