Ich werde einen Kommentarartikel über ein Problem schreiben, das eine Lügenlösungsmethode hat, da es nur wenige Erklärungen gibt, weil es ein altes Problem ist. Insbesondere fiel es mir schwer, weil ich die Erklärung in der Python-Sprache, die ich im Internet verwendete, nicht finden konnte. Ich werde sowohl den Quellcode in der Python-Sprache erklären.
Problemstellung ARC002 C-Befehlseingabe Kommentar Offizieller Kommentar
Listen Sie L und R auf und ersetzen Sie gierig entweder L oder R der Reihe nach. In dieser Lösung ist die Eingabe
8
ABABBABA
Im offiziellen Kommentar wird erklärt, dass es in solchen Fällen falsch sein wird. Die richtige Antwort lautet "4", da es LLRR sein kann, wenn L = AB und R = BA. Wenn es sich um eine Lügenlösungsmethode handelt, ist dies LLBLA oder ARBRR und "5". Da ein solcher Fall jedoch nicht in den Testobjekten enthalten ist, ist er auch mit der Lügenlösungsmethode AC.
Wie im offiziellen Kommentar angegeben, verwenden wir eine dynamische Planung. Ich bin der i-te Brief ・ (J = 0) Anzahl der Zeichen, wenn nicht durch L, R ersetzt ・ (J = 1) Anzahl der Zeichen, wenn sie durch L ersetzt werden ・ (J = 2) Anzahl der Zeichen, wenn sie durch R ersetzt werden Ich habe 3 Zustände gemacht und es gelöst. Diese dp-Tabelle wird als dp [j] [i] geschrieben.
dp [0] [i] ist der Wert, der durch Addieren von +1 zur Mindestanzahl von Zeichen zum Zeitpunkt vor einem Zeichen erhalten wird.
dp[0][i]= min(dp[0][i-1],dp[1][i-1],dp[2][i-1])+1
Da dp [1] [i] und dp [2] [i] die Zeichen i-1 und i durch L oder R ersetzen, wird die Mindestanzahl von Zeichen bis zum Zeichen i-2 um +1 erhöht. Es wird die Anzahl der Zeichen sein.
if c[i-2:i]==L:
dp[1][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
if c[i-2:i]==R:
dp[2][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
Wenn die Zeichen i-1 und i nicht L und R sind und nicht ersetzt werden können ・ Kopiere dp [0] [i] Oder ・ Geben Sie einen Wert ein, der größer als die Antwort ist (N oder float ("inf")). Lassen wir es als. Da der Mindestwert von der dynamischen Planungsmethode übernommen wird, gibt es kein Problem, solange mehr als dp [0] [i] vorhanden ist.
N=int(input())
c=input()
L_list=["AA","AB","AX","AY","BA","BB","BX","BY","XA","XB","XX","XY","YA","YB","YX","YY"]
R_list=["AA","AB","AX","AY","BA","BB","BX","BY","XA","XB","XX","XY","YA","YB","YX","YY"]
ans=N
for L in L_list:
for R in R_list:
dp= [[0]*(N+1) for _ in range(3)] #Obwohl 0 als Anfangswert zugewiesen ist, handelt es sich tatsächlich um einen großen Wert oder die Anzahl der Zeichen.(i)Es ist einfacher, danach zu schreiben, wenn Sie ersetzen
for i in range(1,N+1):
dp[0][i]= min(dp[0][i-1],dp[1][i-1],dp[2][i-1])+1
if i==1:
dp[1][i]= 1
dp[2][i]= 1
else:
if c[i-2:i]==L:
dp[1][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
dp[2][i]=N
elif c[i-2:i]==R:
dp[1][i]=N
dp[2][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
else:
dp[1][i]=N
dp[2][i]=N
tmp=min(dp[0][-1],dp[1][-1],dp[2][-1])
ans=min(ans,tmp)
print(ans)
Diejenigen, die Kommentarartikel in C ++ schreiben Es ist in Ordnung zu vergessen