[Python] ABC175D

Puisque Pi! = I et P1, P2, ..., PN sont tous différents, c'est une boucle qui revient toujours au point de départ, peu importe où vous commencez. A partir de N ≤ 5000, même si le chemin de la boucle est trouvé pour tous les points de départ, ce sera le pire O (N ^ 2), et il semble que ce sera en quelque sorte dans le temps. Par conséquent, considérez-le comme le point de départ ci-dessous. Pour chaque s, suivez les étapes ci-dessous.

Step1 1er point → 2ème point → ・ ・ ・ → Pour la boucle de s (dernier point), trouvez la somme cumulée S de points. Step2 La valeur maximale du score est calculée en classant les observations selon la grandeur de K et len (S). Les cas sont les suivants.

Étape 2 - Cas A: Lorsque K ≤ len (S):

Puisque la boucle n'est pas effectuée pendant une semaine, la valeur maximale de S au point accessible est la réponse.

Étape 2-Cas B: Lorsque K> len (S):

Lorsque S [-1] ≤ 0, il n'y a pas de mérite pendant plus d'une semaine, donc la valeur maximale jusqu'à une semaine, c'est-à-dire la valeur maximale de S est la réponse. Quand S [-1]> 0, je veux tourner autant que je peux, mais en fait, le score peut être plus élevé si je tourne un tour de moins, donc je vais calculer et comparer les scores dans les deux cas.

Référence: [Python] ABC175 Explanation

Exemple de code


N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
for s in range(N):
    ### Step1
    S = []  #Liste de somme cumulée dans la boucle S.pourtant,Le premier terme n'est pas 0 mais le score après le premier coup.
    #1er coup
    i = P[s] - 1
    S.append(C[i])
    #Deuxième coup et mouvements suivants.Répétez jusqu'à ce que vous reveniez au point de départ.
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])

    ### Step2:Cas séparés selon la longueur de K et S,Trouvez le score maximum.
    #Si vous pouvez vous déplacer de moins d'un tour:
    if K <= len(S):
        score = max(S[:K])
    #Il peut dépasser un tour,Lorsque le score diminue à un tour de la boucle:
    elif S[-1] <= 0:
        score = max(S)
    #Peut dépasser une semaine,Et si le score augmente chaque semaine dans la boucle:
    else:
        #Boucle(K // len(S) - 1)En tournant:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        #Boucle(K // len(S))En tournant:
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        #Le plus grand de score1 et score2 est le score maximum dans ce cas.
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)

Recommended Posts

[Python] ABC175D
[Python] DP ABC184D
[Python] UnionFind ABC177D
Résoudre ABC168D en Python
Résolvez ABC167-D avec Python
Python
[Python] Recherche de bisection ABC155D
Résoudre ABC159-D en Python
[Python] Somme cumulée ABC179D
[Python] BFS (recherche de priorité de largeur) ABC168D
[Python] DFS (recherche de priorité en profondeur) ABC157D
python kafka
Les bases de Python ⑤
Résumé Python
Python intégré
Technique Python
Étudier Python
Compte à rebours Python 2.7
Mémorandum Python
astuces python
fonction python ①
Les bases de Python
Mémo Python
ufo-> python (3)
[Python] Comment dériver nCk (ABC156-D)
Installer python
Python Singleton
Les bases de Python ④
Mémorandum Python 2
mémo python
Python Jinja2
Incrément Python
atCoder 173 Python
[Python] fonction
Installation de Python
Installer Python 3.4.3.
Essayez Python
Itératif Python
Algorithme Python
Python2 + mot2vec
[Python] Variables
Fonctions Python
Python sys.intern ()
Tutoriel Python
Fraction Python
underbar python C'est ce que
Démarrer python
[Python] Trier
Remarque: Python
Sortie du journal python
Les bases de Python
[Scraping] Scraping Python
Mise à jour Python (2.6-> 2.7)
mémo python
Mémorandum Python
Python #sort