writer: ir5 tester: misof, ivan_metelsky, rng_58

Div2-600
Div1-275
「Stamp」解説
writer: ir5
tester: misof, ivan_metelsky, rng_58
問題設定
1×N の長方形がある．各セルに次の手順で色を塗りたい
• 好きな長さのスタンプを1つだけ作る (この長さを L とする)
• スタンプを好きなだけ押す：まず，好きな色を選び，
続いて好きな場所(連続した L 個のセル)に色を塗る．
スタンプを押そうとしてる場所に，選んだ色と違う色が
塗られたセルがあるとき，そこにはスタンプを押せない．
最終的に各セルの色を与えられたパターンにしたい．
*
*
問題設定 (cont.)
1×N の長方形がある．各セルに次の手順で色を塗りたい
塗り終わった後，
L×stampCost + (スタンプを押した回数)×pushCost
だけコストが発生する．必要なコストを最小化せよ．
Constraints: N ≤ 50
*
*
Example 0
stampCost = 1
pushCost = 1
みたいなとき，スタンプのサイズを L=2 にして ↓ みたいに押す．
コストは 1*2 + 3*1 = 5 でこれが最小．
解法 (「*」無し)
とりあえず「*」無しで考えてみる．
N ≤ 50 とかなのでスタンプのサイズ L を固定してみる．
• 「色を上書きできない」という制約から，色をまたぐことはできない．
• 各色のカタマリ(連結成分)ごとに考えればいい．
解法 (「*」無し)
左から順に押せば長さ x の連結成分はceil(x / L) 回で押せるので，
単に連続する色の長さを調べればいい．
解法 (「*」有り)
「*」があるときは連結成分の”切れ目”がわからない．
→ スタンプを押す回数が最小になる切れ目を探せばいい．
dp[i] := セル[i.. N] について問題を解く時のスタンプ使用回数
とすると，i から次の切れ目位置を k として
dp[i] = min i+L ≤ k ceil((k – i) / L) + dp[k] (ただしセル[i..k]は1色で塗れる)
とかになる．
計算量は O(N3) とか O(N4)．
k
i
*
*

Download Report