SRM558 Div1 275

問題

N個の1列に並んだセルからなる真っ白なボードがあり、これに色をつけたい。各セルの色は赤、青、緑の3色。
各セルの塗りたい色desiredColorが与えられ、R,G,Bならばその対応した色、*ならばどれでもよい、を表す。
色をつけるときはL個分の隣接セルをまとめて色をつけるスタンプを用意する。L個分のスタンプはコストL*stampCostだけかかる。
スタンプができたら、そのスタンプだけを使って、色を変えながらセルに色をつけていく。
スタンプをある色にして、ある連続したL個のセルに色をつけるには毎回コストpushCostだけかかる。また、色をつけるとき、既に別な色が塗られている場合は色をつけられず、同じ色か無色ならば色をつけられる。

スタンプを作るコストと色をつけるコストの合計で、最小となる時の総コストを求める。

考え方

L=1の時は必ず色をつけられる。そのときのコストは「stampCost+N*pushCost」。
以下、Lが2〜Nまでそれぞれについて考え、最小のコストを返す。

Lが決まったとすると、求めたいのは色をつける「最小回数」になる。なぜなら「L*stampCost+最小回数*pushCost」なので。

まず、*がない場合は、ある色がx(>=L)セル連続していたとき、そこをceil(x/L)回で求められるので、すべての色についてその合計を求めればよい。
問題は、*がある場合で、dp[i]をiからN-1までのセルを塗るときの最小回数として漸化式をたてると、
dp[i] = min(iからx個同じ色が連続していれば、「ceil(x/L) + dp[i+x]」回)
となるので、これを求める。

desiredColor[i]が*の時は、desiredColor[i]がR,G,Bそれぞれだと仮定しそれらで最小のdp[i]を選んで、色が連続しているかどうかの判定では、desiredColor[i]と同じ色と仮定して計算する。
x個連続できないところがあるときはdp[i]を大きな値のままなどにしておけばよく(L=1の方が小さいので)、オーバーフローしないよう気をつけるだけでよい。

各Lについて最小回数をもとめて、そのコストで最小のものを返せばよい。