[Python] [Erklärung] AtCoder Typischer DP-Wettbewerb: Ein Wettbewerb

Link zum Problem: https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

Einführung

AtCoder-Version! Arimoto (Anfänger) hat dieses Problem eingeführt, aber es gab keine offizielle Erklärung, wahrscheinlich aufgrund eines alten Wettbewerbs.

Ich konnte es nicht selbst lösen, also habe ich AC, während ich mir die Erklärung zu [diesem Artikel] angesehen habe (http://garnacha.techblog.jp/archives/38634648.html). Ich werde meinen Code hier als Referenz einfügen. (Da DP studiert, kann die Genauigkeit nicht garantiert werden.)

Ich habe viele Kommentare hinzugefügt, um das Verständnis zu erleichtern.

Implementierung

#Eingaben empfangen
N = int(input())
P = list(map(int, input().split()))

#Ist es möglich, mit den Fragen bis zur i-Frage (Bool-Wert) insgesamt j Punkte zu bekommen?
DP = []
#[N]
for i in range(N+1):
    # N=
    #**100+1）
    a = [False] * (100 * 101)
    DP.append(a)

#=Wenn Sie bis zu 100 benötigen und alle Ps 100 Punkte sind, beträgt der maximale Gesamtwert 100 bis 100 Punkte (die Arraygröße kann 0 Punkte betragen. Verwenden Sie also die Fragen bis zur 100. Frage (eine Frage). Ich kann es nicht lösen) Ich kann 0 Punkte bekommen.
#Da es sich nicht um eine andere Punktzahl handelt, ist DP[0][0]DP anders als[0]Der Wert des Arrays von ist False.
DP[0][0] = True

#Schleife von der 1. Frage zur N-ten Frage
for i in range(1, N+1):
    # DP[i]DP, um den Wert einzugeben[i-1]Um den Zustand von zu sehen
    for j, dpj in enumerate(DP[i-1]):
        if dpj is True:
            #Lösen Sie das i-question-Problem nicht
            DP[i][j] = True

            #Lösen Sie das i-Frage-Problem
            #Die Punktzahl der i-Frage ist P.[i-1]Vertreten durch
            DP[i][j+P[i-1]] = True

ans = 0
# DP[N]Betrachtet man das Array von, so kann die Gesamtpunktzahl wahr sein
for dpi in DP[N]:
    if dpi is True:
        ans += 1
print(ans)

Konkretes Beispiel

Ich denke, es ist schwierig, ein Bild nur durch Implementierung zu erhalten. Schauen wir uns also den Inhalt des DP-Arrays am Beispiel von "Sample Input 1" an.

`Sample_Input_1`


#Eingang
3
2 3 5

#Ausgabe
７

Unten finden Sie den Inhalt der DP-Sequenz. Es zeigt an: "Kann ich j Punkte bekommen, wenn ich die i-te Frage gelöst habe?" Von der Probeneingabe beträgt der Maximalwert von j 10 (2 + 3 + 5).

i\j	0	2	3	5	7	8	10
0	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0
2	1	1	1	1	0	0	0
3	1	1	1	1	1	1	1

Wenn i = 0 ist, dh wenn das Problem nicht gelöst ist, ist die einzig mögliche Punktzahl 0. (Nur DP [0] [0] ist wahr) Wenn i = 1 ist, dh wenn Sie nur die erste Frage gelöst haben, ist die mögliche Punktzahl 0 oder 2. (Die Punktzahl der ersten Frage beträgt 2 Punkte) Wenn i = 2, sind die möglichen Punkte 0 Punkte, 2 Punkte, 3 Punkte und 5 Punkte. (Da die Punktzahl der zweiten Frage 3 Punkte beträgt, addieren Sie 3 Punkte zu der Punktzahl, die bei i = 1 wahr ist oder nicht) Wenn eine solche Operation bis zu i = 3 ausgeführt wird, ist True "0, 2, 3, 5, 7, 8, 10", also lautet die Antwort 7.

das ist alles.