In dem Kommentarartikel des Abschnitts DP ( Referenz ) gab es einen Teil, den ich persönlich nicht verstehen konnte. Ich werde versuchen, es zu erklären, indem ich es persönlich kaue. (Möglicherweise liegt ein Fehler beim Verstehen vor ...)
Die folgenden zwei Punkte konnten nicht verstanden werden
・ Weil der Index bei 0 beginnt ・ Wenn 0 <= l, r <n, können die folgenden Ausdrücke verwendet werden.
・ Weil ich den Abschnittsunterteilungspunkt (Mitte im obigen Referenzartikel) als rekursiven Ausdruck verwenden möchte. Wenn der Ausdruck auf beiden Seiten geschlossen ist (dh das Intervall [l, r]), ist die Division wie folgt.
Im Referenzartikel wurden die Fälle wie folgt aufgeteilt.
In Fall 1 verschwinden alle Teile, die zwischen beiden Enden angeordnet sind, und die verbleibenden Enden verschwinden. Wie eine Kette von Puyopuyo. Fall 2 ist ein Fall, in dem die maximale Anzahl von Entfernungen für jedes Teil erhalten wird, indem es in zwei Teile geteilt wird.
Gibt es einen anderen Fall für meine Frage? Das ist. Ich habe den Grund für MECE in 2 Fällen nicht verstanden. Was ist zum Beispiel mit dem Fall, in dem der zwischen beiden Enden eingeklemmte Teil verschwindet und zwei übrig bleiben und die verbleibenden zwei zusammen mit beiden Enden verschwinden? (Fall A) Was ist mit dem Fall, in dem der zwischen beiden Enden eingeklemmte Teil verschwindet und einer übrig bleibt und der verbleibende Teil mit einem der beiden Enden verschwindet? (Fall B)
Als ich es in die Abbildung schrieb, stellte ich fest, dass es im zweiten Fall enthalten war. (Ich konnte nicht beweisen, dass es in zwei Fällen passt)
| Fall A.  | ケースB |
import sys
sys.setrecursionlimit(250000)
input = sys.stdin.readline
dp = []
w =[]
def rec(l,r):
#Wenn es bereits durchsucht wurde, wird sein Wert zurückgegeben.
if dp[l][r] >= 0:
return dp[l][r]
#0, da ein einzelner Fall nicht gelöscht werden kann
if l == r:
dp[l][r] = 0
return 0
#Bei durchgehenden Teilen
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
#Fall 1 Alle zwischen beiden Enden eingeklemmten Teile verschwinden und die verbleibenden beiden Enden verschwinden
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: #Fall 2 Der zwischen beiden Enden eingeklemmte Teil verschwindet nicht
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()