ABC#004 D.マーブル

問題

無限に長い一直線上に箱が並んでおり、-100のところに赤玉がR個、0のところに緑玉がG個、100のところに青玉がB個ある。
1回の操作で、一つの玉を左右どちらかに移すことができるが、同じ箱に違う色の玉をいれる状態を作ってはいけない。
すべての箱に玉が1つ以下の状態にするまでの最小操作回数を答える。

考え方

greedyにやろうと考えると、Gが300個の時、どちらにはみ出した方がよいか？を考えないといけない。
(RかBの少ないほうに寄せた方がよい)

効率的に計算するには、動的計画法が使える。
まず、同じ色の玉を隙間をあけず、伸ばすように広げた場合が最適だとわかる。
また、R,G,Bは広がった時かぶりはない。
赤玉をa〜bまでの箱を使った場合は、何回移動するかは最初の箱の位置から計算できるので、
dp[i][j]:=色iまでを使って、j-1までの位置の箱まで使った場合、最小で何回で広げることができているか
を計算。新しい色はj以降で広げればよいので、R,G,Bの順で試す。