$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$
◇◇ref043:Educational Codeforces Round 83 - E : Array Shrinking◇◇
☆問題URL
https://codeforces.com/contest/1312/problem/E
☆問題の概要
$N$要素の数列$A$が与えられ、$A$に対して以下の操作を繰り返す。
-
$A$のなかで同じ整数$a$が隣り合っている場所を選び、その2つの整数$a$を1つの整数$a+1$に置き換える。
最適に操作を行ったとき、数列の長さを最小でいくつにできるか答えよ。
☆解法
DPテーブルを
-
$val[l][r]=$区間$[l, r)$を1つの整数にまとめられるとき、その値がいくつになるか
-
$len[l][r]=$区間$[l, r)$で最適に操作したときの数列の長さ
とする(区間DP)。ここで、各$l, r$について$l\lt k\lt r$となるような$k$で
-
$val[l][k]==val[k][r]$ならば、$val[l][r]=val[l][k]+1$
-
$val[l][k]==val[k][r]$ならば$len[l][r]=1$、そうでなければ$len[l][r]=\text{chmin}(len[l][k]+len[k][r])$
のように更新する。これはある区間を1つの整数に縮約できるとき、必ずその整数は1通りに定まることを利用している。最後に、$len[0][N]$を出力すればよい。
☆反省
$N\leq 500$でO($N^3$)が通りそうな感じなので、コンテスト中は絶対貪欲だろうなと思っていろいろ試していた。コンテスト後のタイムラインで得た情報によると、こういう系(数列を縮約したり区間にいろいろする問題)では区間DPは鉄板らしい。区間DPはメモ化再帰にするとかなり書きやすくなる。
戻る