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

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

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.