Codeforces Round #230 (Div. 1) E. Deleting Substrings

暗黒時代のCFなのはわかるがEditorialぐらい復活させてくれ :@
http://codeforces.com/contest/392/problem/E

概要

N要素からなる数列{w}がある。以下の操作を繰り返して、スコアを最大化せよ

• 数列の連続する部分を取り除き、その長さをLとすると、v[L]点稼げる。ただし、取り除く部分は隣接する項が絶対値で1ずつ異なっていて、山型でなければならない。(➚→➘)（操作が終わると、取り除かれた部分の左と右はくっつく。また、全部消さなくて途中で終わっても良い）

N<=400 , |v[i]|<=2000 w[i]<=10^9

解法

DP

con[i][j]:=w[i],w[j-1]を公差1,-1の等差数列で結ぶとき、{w}の[i...j)で余ってしまうものを先に使うことになる。先に使うもののスコアの最大値
dp[i][j]:=w[i],w[j-1] を両端とする山型の形を作るときの、その範囲のスコアの最大値。{w}の[i...j)での山型の形の数列に入らないものは先にすべて使うことになる。
dp2[i][j]:={w}の[i...j)をすべて使うときのスコアの最大値。

このDPができると、
res[i]:=[0...i)までのスコアの最大値
をdp[i][j]を使って更新できる。

上のDPは、j-iが短い順にやると実はできる.
con[i][j]は、iの次のくるものを[i+1,j)の中で全部調べる。
dp[i][j]は、山のてっぺんになるものを[i,j)の中で全部調べる。
dp2[i][j]は、dp[i][j]を代入したあと、分割される場所を全部調べる。
時間O(n^3),空間O(n^2)
http://codeforces.com/contest/392/submission/7438155