区間DPの解説記事で(参考)、個人的に理解できない箇所があったので、個人的に咀嚼して説明してみる。
（理解に誤りがあるかもしれないが。。。）
理解できなかった箇所は以下の２点
１．なぜ右側解放？
２．２ケースに分けているが、他のケースは無いのか？
１．なぜ右側解放?
・ただ単にindexが0始まりだから
・0<=l,r<nの場合は以下の表現でも良さそう
※AOJでTLEするけど、それっぽいソースを最下部に張り付けておく。
- dp[l][r] := 区間[l , r]で取り除くことのできるブロックの数
・区間分割点（上記参考記事ではmid）をそのまま使って再帰表現をしたいから
両側が閉じた表現にした場合（つまり区間[l , r]）、以下の分け方になる。
- [l,mid] , [mid+1 , r]に区間を分ける
２．２ケースに分けているが、他のケースは無いのか？
参考記事では以下の様にケース分けをしていた。
- 1. lのブロックとr - 1のブロックが対になれる
- 2. [l,mid) , [mid , r)に区間を分ける
1.のケースは、両端に挟まれている箇所がすべて消えて、さらに残った両端が消えるケース。ぷよぷよの連鎖みたいに。
2.のケースは、２分割してそれぞれのパート毎に最大の除去数を求めるケース
自分の疑問は、他にケースは無いのか？ということ。２ケースでMECEとなる理由が分からなかった。
たとえば、両端に挟まれている箇所が2個を残し消えて、さらに残った2個が両端とともに消えるケースはどうなのか？(ケースA)
両端に挟まれている箇所が1個を残し消えて、さらに残った1個が両端のいずれかとともに消えるケースはどうなのか？(ケースB)
図に書いてみると、2のケースに含まれることがわかった。
（２ケースに収まるという証明ができたわけではない）
ケースA
|
ケースB
|
import sys
sys.setrecursionlimit(250000)
input = sys.stdin.readline
dp = []
w =[]
def rec(l,r):
#既に探索済の場合はその値を返す
if dp[l][r] >= 0:
return dp[l][r]
#単一ケースは落とせないので0
if l == r:
dp[l][r] = 0
return 0
#連続している箇所の場合
if l + 1 == r:
if abs(w[l] - w[r]) <= 1:
dp[l][r] = 2
return 2
else:
dp[l][r] = 0
return 0
res = 0
#Case1 両端に挟まれている箇所がすべて消えて、さらに残った両端が消える
if abs(w[l] - w[r]) <= 1 and rec(l+1, r-1) == (r - 1) - (l + 1) + 1:
res = (r - 1) - (l + 1) + 1 + 2
else: #Case2 両端に挟まれている箇所が消えない
for mid in range(l,r):
res = max(res, rec(l,mid)+rec(mid+1,r))
dp[l][r]=res
return res
def main():
global w
global dp
n_list=[]
w_list=[]
while True:
n = int(input())
if n == 0 :
break
w_tmp = list(map(int, input().split()))
n_list.append(n)
w_list.append(w_tmp)
for i in range(len(n_list)):
dp = [[-1] * n_list[i] for j in range(n_list[i])]
w = w_list[i]
print(rec(0,n_list[i]-1))
main()