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