Educational Codeforces Round 83 (Rated for Div. 2) E. Array Shrinking

Educational Codeforces Round 83 (Rated for Div. 2) E. Array Shrinking)

問題

隣り合う要素の値が同じ場合、それらを結合し、+1した値に置換える操作を繰り返したとき、長さの最小値。

解説

区間DP。

dp[i][j]: 区間[i,j)についての操作後の長さの最小値
val[i][j]: dp[i][j] == 1の場合のみ、その値を記録する

とする。

例によって長さの短いものから決めていく。 区間[l,r)の結果を決めるために必要なのは、区間[l,mid)と 区間[mid, r)の結果である(l + 1 <= mid < r)。これらは区間[l,r)より短いものであり、それらは前計算で全て求まっているとする。midの仕切りで挟まれた結果両方が長さ1になっていて、かつ値(val)が同じ場合、結合することで長さを1にできる。それ以外の場合、左右を結合せずにただ連結する。

O (N^3)

提出

- for文

- メモ化再帰

参考

• けんちょんの競プロ精進記録 Educational Codeforces Round 83 E. Array Shrinking