[Python] [Explication] Concours DP typique d'AtCoder: un concours

Lien vers le problème: https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

introduction

Version AtCoder! Arimoto (Débutant) a introduit ce problème, mais il n'y avait aucune explication officielle, probablement à cause d'un ancien concours.

Je n'ai pas pu le résoudre moi-même, donc j'ai AC en regardant l'explication de cet article. Je vais mettre mon code ici pour référence. (Étant donné que DP étudie, la précision ne peut être garantie)

J'ai ajouté de nombreux commentaires pour faciliter la compréhension.

la mise en oeuvre

#Réception d'entrée
N = int(input())
P = list(map(int, input().split()))

#Est-il possible d'obtenir un total de j points en utilisant les questions jusqu'à la i-question (valeur booléenne)?
DP = []
#La 0ème question est supposée être dans un état où aucun problème n'a été résolu. Il y a N questions, donc DP[N]Besoin de
for i in range(N+1):
    # N=Si 100 et tous les P valent 100 points
    #La valeur maximale du total est de 100*100 points (la taille du tableau est de 100 car elle peut être de 0 point)*100+1)
    a = [False] * (100 * 101)
    DP.append(a)

#En utilisant les questions jusqu'à la 0e question (=Vous pouvez obtenir 0 point (ne résolvez aucun problème).
#Aussi, comme ce ne sera pas un score autre que ça, DP[0][0]DP autre que[0]La valeur du tableau de est False.
DP[0][0] = True

#Boucle de la 1re question à la nième question
for i in range(1, N+1):
    # DP[i]DP pour mettre la valeur[i-1]Je vais regarder l'état de
    for j, dpj in enumerate(DP[i-1]):
        if dpj is True:
            #Ne résolvez pas le problème i-question
            DP[i][j] = True

            #Résolvez le problème i-question
            #Le score de la question i est P[i-1]Représenté par
            DP[i][j+P[i-1]] = True

ans = 0
# DP[N]En regardant le tableau de, le score total qui peut être vrai
for dpi in DP[N]:
    if dpi is True:
        ans += 1
print(ans)

Exemple concret

Je pense qu'il est difficile d'obtenir une image simplement en l'implémentant, alors jetons un coup d'œil au contenu du tableau DP en utilisant "Sample Input 1" comme exemple.

Sample_Input_1


#contribution
3
2 3 5

#production
7

Voici le contenu de la séquence DP. Il indique «Puis-je obtenir j points lorsque j'ai fini de résoudre la i-ème question? À partir de l'entrée d'échantillon, la valeur maximale de j est 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

Lorsque i = 0, c'est-à-dire lorsque le problème n'est pas résolu, le seul score possible est 0. (Seul DP [0] [0] est vrai) Lorsque i = 1, c'est-à-dire lorsque vous avez terminé de résoudre uniquement la première question, le score possible est de 0 ou 2. (Le score de la première question est de 2 points) Lorsque i = 2, les points possibles sont 0 point, 2 points, 3 points et 5 points. (Puisque le score de la deuxième question est de 3 points, ajoutez 3 points au score qui est Vrai à i = 1 ou non) Lorsqu'une telle opération est effectuée jusqu'à i = 3, True est "0, 2, 3, 5, 7, 8, 10", donc la réponse est 7.

c'est tout.

Recommended Posts

[Python] [Explication] Concours DP typique d'AtCoder: un concours
AtCoder Beginner Contest 166 A Explication du problème "A? C" (Python3, C ++, Java)
AtCoder Beginner Contest 167 Explication d'un problème "enregistrement" (Python3, C ++, Java)
AtCoder Beginner Contest 169 Explication du problème "Multiplication 1" (Python3, C ++, Java)
AtCoder Beginner Contest 176 A Explication du problème "Takoyaki" (Python3, C ++, Java)
AtCoder Beginner Contest 175 Explication d'un problème "Saison des pluies" (C ++, Python3, Java)
AtCoder Beginner Contest 174 Explication d'un problème "Climatiseur" (C ++, Python, Java)
AtCoder Beginner Contest 177 Explication du problème "Ne soyez pas en retard" (Python3, C ++, Java)
AtCoder Beginner Contest 165 Un problème Explication "We Love Golf" (Python3, C ++, Java)
AtCoder ABC 177 Python (A ~ E)
Concours de programmation Atcoder Acing Python
AtCoder Beginner Contest 176 Explication de l '«étape» du problème C (Python3, C ++, Java)
AtCoder ABC 176 Python (A ~ E)
AtCoder ABC 182 Python (A ~ D)
Concours Atcoder Débutant 152 Kiroku (python)
AtCoder Beginner Contest 174 B Explication du problème "Distance" (C ++, Python, Java)
AtCoder Beginner Contest 177 B Explication du problème "Sous-chaîne" (Python3, C ++, Java)
[Explication AtCoder] Contrôle ABC180 Problèmes A, B, C avec Python!
[Explication AtCoder] Contrôle ABC158 Problèmes A, B, C avec Python!
AtCoder Beginner Contest 175 Tâche A - Réponse vivante de la saison des pluies (Python)
AtCoder Beginner Contest 169 B Problème Explication "Multiplication 2" (Python3, C ++, Java)
[Explication AtCoder] Contrôle ABC164 Problèmes A, B, C avec Python!
[Explication AtCoder] Contrôle ABC168 Problèmes A, B, C avec Python!
Explication ABC127 A, B, C (python)
[Python] Maintenant un codeur marron ~ [AtCoder]
Modèle AtCoder ABC 179 Python (A ~ E)
Explication ABC126 A, B, C (python)
AtCoder Beginner Contest 174 C Problème (Python)
[Python] Maintenant un codeur vert ~ [AtCoder]
atCoder 173 Python
AtCoder Beginner Contest 175 B Explication du problème "Making Triangle" (C ++, Python3, Java)
AtCoder Beginner Contest 176 B Problème Explication "Multiple of 9" (Python3, C ++, Java)
[AtCoder] Résoudre ABC1 ~ 100 Un problème avec Python
Résoudre AtCoder ABC168 avec python (A ~ D)
Concours pour débutants AtCoder: Réponses aux problèmes D Python
AtCoder Beginner Contest 173 B Problème Explication du "Récapitulatif de l'état du juge" (Python3, C ++, Java)
[Explication AtCoder] Contrôlez les problèmes A, B, C d'ABC182 avec Python!
AtCoder Beginner Contest 170 B Problème Explication "Crane and Turtle" (Python3, C ++, Java)
AtCoder Beginner Contest 177 Explication du problème C "Somme des produits de paires" (Python3, C ++, Java)
[Explication AtCoder] Contrôle ABC184 Problèmes A, B, C avec Python!
AtCoder Beginner Contest 167 B Problème Explication de "Programmation linéaire facile" (Python3, C ++, Java)
Concours AtCoder Débutant 177
[AtCoder] Résoudre un problème de ABC101 ~ 169 avec Python
Concours AtCoder Débutant 179
[Python] Concours de programmation Sumitomo Mitsui Trust Bank 2019 C (Comment utiliser DP) [AtCoder]
AtCoder ABC 174 Python
[Explication AtCoder] Contrôlez les problèmes A, B, (C), D de ABC165 avec Python!
[Python] DP ABC184D
[Explication AtCoder] Contrôlez les problèmes A, B, C, D d'ABC183 avec Python!
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Script Python pour obtenir une liste d'exemples d'entrée pour le concours AtCoder
Concours Atcoder Débutant 153
Défiez AtCoder (ABC) 164 avec Python! Un problème ~ C
[Explication AtCoder] Contrôlez les problèmes A, B, C, D d'ABC181 avec Python!