[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
7

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 1 2 3 4 5 6 7 8 9 10 ...
0 1 0 0 0 0 0 0 0 0 0 0
1 1 0 1 0 0 0 0 0 0 0 0
2 1 0 1 1 0 1 0 0 0 0 0
3 1 0 1 1 0 1 0 1 1 0 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.

Recommended Posts

[Python] [Erklärung] AtCoder Typischer DP-Wettbewerb: Ein Wettbewerb
AtCoder Anfängerwettbewerb 166 A Erklärung des Problems "A? C" (Python3, C ++, Java)
AtCoder Anfängerwettbewerb 167 Ein Problem "Registrierung" Erklärung (Python3, C ++, Java)
AtCoder Beginner Contest 169 Eine Erklärung des Problems "Multiplikation 1" (Python3, C ++, Java)
AtCoder Beginner Contest 176 Eine Erklärung des Problems "Takoyaki" (Python3, C ++, Java)
AtCoder Anfängerwettbewerb 175 Ein Problem "Regenzeit" Erklärung (C ++, Python3, Java)
AtCoder Anfängerwettbewerb 174 Ein Problem "Klimaanlage" Erklärung (C ++, Python, Java)
AtCoder Anfängerwettbewerb 177 Eine Erklärung des Problems "Sei nicht zu spät" (Python3, C ++, Java)
AtCoder Anfängerwettbewerb 165 Ein Problem "Wir lieben Golf" Erklärung (Python3, C ++, Java)
AtCoder ABC 177 Python (A ~ E)
Atcoder Acing Programmierwettbewerb Python
AtCoder Anfängerwettbewerb 176 C Problem "Schritt" Erklärung (Python3, C ++, Java)
AtCoder ABC 176 Python (A ~ E)
AtCoder ABC 182 Python (A ~ D)
Atcoder Anfänger Wettbewerb 152 Kiroku (Python)
AtCoder Anfängerwettbewerb 174 B Problem "Entfernung" Erklärung (C ++, Python, Java)
AtCoder-Anfängerwettbewerb 177 B Problem "Teilzeichenfolge" Erläuterung (Python3, C ++, Java)
[AtCoder Erklärung] Kontrollieren Sie ABC180 A, B, C Probleme mit Python!
[AtCoder Erklärung] Kontrollieren Sie ABC158 A, B, C Probleme mit Python!
AtCoder Anfängerwettbewerb 175 Aufgabe A - Lebendige Antwort in der Regenzeit (Python)
AtCoder-Anfängerwettbewerb 169 B Problem "Multiplikation 2" Erläuterung (Python3, C ++, Java)
[AtCoder Erklärung] Kontrollieren Sie ABC164 A, B, C Probleme mit Python!
[AtCoder Erklärung] Kontrollieren Sie ABC168 A, B, C Probleme mit Python!
ABC127 A, B, C Erklärung (Python)
[Python] Jetzt ein brauner Codierer ~ [AtCoder]
Vorlage AtCoder ABC 179 Python (A ~ E)
ABC126 A, B, C Erklärung (Python)
AtCoder Anfängerwettbewerb 174 C Problem (Python)
[Python] Jetzt ein grüner Codierer ~ [AtCoder]
atCoder 173 Python
AtCoder Anfängerwettbewerb 175 B Problem "Making Triangle" Erklärung (C ++, Python3, Java)
AtCoder-Anfängerwettbewerb 176 B Problem "Multiple of 9" Erläuterung (Python3, C ++, Java)
[AtCoder] Löse ABC1 ~ 100 Ein Problem mit Python
Löse AtCoder ABC168 mit Python (A ~ D)
AtCoder Anfängerwettbewerb: D Problemantworten Python
AtCoder-Anfängerwettbewerb 173 B Problem "Zusammenfassung des Richterstatus" Erläuterung (Python3, C ++, Java)
[Erklärung zum AtCoder] Kontrollieren Sie die A-, B- und C-Probleme von ABC182 mit Python!
AtCoder Anfängerwettbewerb 170 B Problem "Crane and Turtle" Erklärung (Python3, C ++, Java)
AtCoder Beginner Contest 177 Erklärung des C-Problems "Summe der Produktpaare" (Python3, C ++, Java)
[AtCoder Erklärung] Kontrollieren Sie ABC184 A, B, C Probleme mit Python!
AtCoder-Anfängerwettbewerb 167 B Problem "Einfache lineare Programmierung" Erläuterung (Python3, C ++, Java)
AtCoder Anfängerwettbewerb 177
[AtCoder] Lösen Sie ein Problem von ABC101 ~ 169 mit Python
AtCoder Anfängerwettbewerb 179
[Python] Sumitomo Mitsui Trust Bank Programmierwettbewerb 2019 C (Verwendung von DP) [AtCoder]
AtCoder ABC 174 Python
[Erklärung zum AtCoder] Kontrollieren Sie die A-, B-, (C), D-Probleme von ABC165 mit Python!
[Python] DP ABC184D
[AtCoder-Erklärung] Kontrollieren Sie die A-, B-, C- und D-Probleme von ABC183 mit Python!
AtCoder Anfängerwettbewerb 172
AtCoder Anfängerwettbewerb 180
AtCoder Anfängerwettbewerb 173
Python-Skript zum Abrufen einer Liste von Eingabebeispielen für den AtCoder-Wettbewerb
Atcoder Anfänger Wettbewerb 153
Fordern Sie AtCoder (ABC) 164 mit Python heraus! A ~ C Problem
[Erklärung zum AtCoder] Kontrollieren Sie die A-, B-, C- und D-Probleme von ABC181 mit Python!