LeetCode Remove Boxes
要素数$ Nの数列が与えられる。数列が空になるまで以下の操作を繰り返す時、得点の合計の最大値はいくつか。
同じ数が連続する長さ$ 1以上の区間を選んで取り除く。この時、その区間の長さを$ nとすると、$ n^2の得点を得る。
例:
$ 1, 3, 2, 2, 2, 3, 4, 3, 1
→$ 1, 3, (2, 2, 2), 3, 4, 3, 1($ 2の区間を取り除き、得点$ 3^2を得る)
→$ 1, 3, 3, (4), 3, 1($ 4を取り除き、得点$ 1^2を得る)
→$ 1, (3, 3, 3), 1($ 3の区間を取り除き、得点$ 3^2を得る)
→$ (1, 1)($ 1の区間を取り除き、得点$ 2^2を得る)
得点は$ 23で、これが最大。
制約:
$ 1 \leq N \leq 100
---
$ i番目の要素を$ A_iと表す($ 1 \leq i \leq N)。
$ 1 \leq l, r \leq N,$ 0 \leq k \leq Nとして$ f(l, r, k)を以下のように定める。
$ A_l, A_{l+1}, \ldots, A_{r}と$ k個の $ A_rを連結した数列に対する求める答え
例えば $ 1, 2, 3, 4のもとで$ f(2, 3, 2)は$ 2, 3と$ 3, 3を連結した数列である$ 2, 3, 3, 3に対する答えを表す。
$ f(l, r, k)を漸化式で表すことを考える。対象とする数列について、一度目の区間の選び方として右端の$ k+1個の連続した要素を選ぶというものが考えられる。この場合は$ (k+1)^2 + f(l, r-1, 0)が答えとなる。
上記が最大値でないとすれば、右端の$ k+1個の連続した要素は、$ A_l, A_{l+1}, \ldots, A_{r-1}のどれかの要素と一緒に消すこととなる。
$ A_l, A_{l+1}, \ldots, A_{r-1}のうち$ A_i = A_{r}を満たす$ iについて、これが右端の$ k+1個の要素と一緒に消されるとする。
まず$ A_{i+1}, A_{i+2}, \ldots, A_{r-1}を消す必要があるため、得点$ f(i+1, r-1, 0)が得られる。
その後、末端には同じ値が$ k+2個並ぶ形となり、得点は$ f(l, i, k+1)となる。
合わせて、この場合の答えは$ f(i+1, r-1, 0) + f(l, i, k+1)となる。
また、問題の答えは$ f(1, N, 0)となる。
ということでこの漸化式をメモ化再帰すれば、$ f(l, r, k)は高々$ N^3通りで、それぞれの処理が$ O(N)のため、$ O(N^4)で解ける。
---
ため息しか出ない見事な漸化式。