かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

JOI2016本選 A - オレンジの出荷 (Oranges)

解説 JOI 競技プログラミング 動的計画法

問題はこちら

問題概要

{1\le N\le 20000}個のオレンジの大きさが{1\le A_i\le 10^9}として与えられるとき, 全てのオレンジを箱詰めすることを考える. 一つの箱のコストは{0\le K\le 10^9}で, {1\le M\le 1000}個のオレンジを詰めることができ, 詰めるオレンジは連続した順番のものしか同じ箱に詰めることはできない. ある箱にいくつかのオレンジを詰めるためにかかるコストは, 箱に詰める最大のオレンジの大きさを{a}, 箱に詰める最小のオレンジの大きさを{b}, 箱に詰めるオレンジの個数を{s}としたときに, {K+s×(a−b)}となる. すべてのオレンジを詰めるときの最小コストを求めよ.

思考の流れ

DPっぽい. どんな状態をもってDPするか. 箱の個数は持ってても意味ない. 連続したオレンジを一つにするから, 前からいくつまで見たかはいる. 今詰めようとしてる箱に入ってるオレンジの数や大きさの最大値/最小値なんかは持てない. 前からいくつという情報だけでやる.

{dp[i]}を「{i}番目までのオレンジを箱に詰めた時のの最小コスト」とすると, 更新式は

{dp[i]=\min_{1\le j\lt M-1}(dp[i-j]+k+j×(a_{ij}-b_{ij}))} ({a_{ij}/b_{ij}}は{i}番目のオレンジ以前の連続した{j}個のオレンジの大きさの最大値/最小値)

更新式の意味は, {i-j}番目までのオレンジを詰めて, {i-j+1}から{i}番目までのオレンジを同じ箱に詰める感じ.

{\downarrow}

最大値/最小値は{1\le j\lt M-1}を回すときに逐次更新していけばいい. よって計算量は{O(NM)}

提出プログラム

https://atcoder.jp/contests/joi2016ho/submissions/12052288

感想

最大値, 最小値を求めるときにSegmentTreeを使ってしまった. 余計にlogが乗るので時間が危ない.