[Python] Concours de programmation Sumitomo Mitsui Trust Bank 2019 C (Comment utiliser DP) [AtCoder]

• Cet article est la base de DP (Dynamic Planning) On suppose que deux problèmes de Kaeru-kun peuvent être résolus.

• Frog1

• Frog2

Il fond en DP! !! !! Il y a eu un problème qui m'a impressionné, je vais donc l'écrire sous forme d'article. Je connais l'idée de DP, mais cela ne correspond pas au problème réel! Peut être utile (peut-être pas w)

Concours de programmation Sumitomo Mitsui Trust Bank 2019C

Difficulty:205 Après avoir lu le problème, une recherche complète et un 6 fois pour la phrase me traversèrent la tête pendant un moment, mais cela semble inutile.

À propos, vous pouvez le résoudre même si vous ne pouvez pas penser à DP. (Je le publierai comme une solution distincte à la fin de l'article.) Mais si vous ne pouvez pas penser à un DP Je pense qu'il faudra environ 15 minutes pour trouver la loi.

** Une solution rapide est essentielle pour augmenter le taux! ** **

Avantages de DP

La bonne chose à propos de DP est (pas limité à DP) Au moment où j'ai réalisé que "ce problème peut être résolu avec DP!" ** Je peux coder avec presque la mort cérébrale ** chose! Alors ** je ne mets pas mes pensées là-dedans **, alors Je pense que ce niveau de problème va pouvoir viser AC en 5 minutes environ!

** Le point est de savoir si vous réalisez que vous pouvez utiliser DP! ** **

Prenons un exemple concret

Quoi qu'il en soit, préparez un cahier et un stylo, Pensons au modèle OK et au modèle NG.

1~99：NG 100,101,102,103,104,105：OK 106~199：NG 200,201,202,203,204,205,206,207,208,209,210：OK 211~299：NG 300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315：OK ...

Pourquoi "200 ~ 205" est-il correct? C'est parce que «100 ~ 105» est ajouté à «100», ce qui est OK à l'origine. Pourquoi «201 ~ 206» est-il correct? C'est parce que «100 ~ 105» est ajouté à «101», ce qui est OK à l'origine. Je vois! Ensuite, si vous ajoutez 100 ~ 105 à chacun des 200 ~ 210` à l'origine OK, cela semble être OK.

Oh, je pense que je peux aller avec DP! Si vous acceptez 0 yen comme OK, ajoutez 100 ~ 105 à 0, ce qui est à l'origine OK, et ce sera OK! Il semble que cela fonctionnera! Il ne vous reste plus qu'à coder! !! !!

répondre

Si vous pensez juste au numéro d'index de DPMap, vous devriez pouvoir mourir de cerveau! De plus, si vous savez que c'est DP au moment où vous lisez le problème, vous n'aurez pas besoin d'un cahier et d'un stylo!

test.py

def I(): return int(input())
X = I()
dp = [0]*(X+1) #0_indexed
dp[0] = 1 #J'accepte 0 yen comme OK!
for i in range(X+1):
    if dp[i]:
        for j in range(100,106):
            if i+j<=X: #Mesures pour "out of lange".
                dp[i+j] = 1
print(dp[-1])

Estimation si DP peut être utilisé

Quand l'exemple concret suivant peut être dérivé de la valeur précédente en donnant des exemples concrets dans l'ordre → Il semble utile de se demander si DP peut être utilisé! !! !!

Une autre solution

Je n'ai pas remarqué DP au premier coup d'œil, alors je l'ai fait ici. La quantité de code est petite, mais je pense qu'il faudra un certain temps pour dériver ce code. (Je me demande si c'est plus rapide pour ceux qui ont l'habitude de trouver une telle loi)

test.py

def I(): return int(input())
X = I()
a,b = divmod(X,100)
print(1 if a*5>=b else 0)

fin!