[GO] [Python] ABC175D

Da Pi! = I und P1, P2, ..., PN alle unterschiedlich sind, ist es eine Schleife, die immer zum Startpunkt zurückkehrt, egal wo Sie beginnen. Ab N ≤ 5000 ist die Schleifenroute, selbst wenn sie für alle Startpunkte gefunden wird, das schlechteste O (N ^ 2), und es scheint, dass sie irgendwie rechtzeitig sein wird. Betrachten Sie es daher als Ausgangspunkt s unten. Befolgen Sie für jedes s die folgenden Schritte.

Step1

1. Punkt → 2. Punkt → ・ ・ ・ → Finden Sie für die Schleife von s (letzter Punkt) die kumulative Summe S von Punkten. Step2 Der Maximalwert der Punktzahl wird berechnet, indem die Fälle nach der Größe von K und len (S) klassifiziert werden. Die Fälle sind wie folgt.

Schritt 2 - Fall A: Wenn K ≤ len (S):

Da die Schleife eine Woche lang nicht durchgeführt wird, ist der Maximalwert von S am erreichbaren Punkt die Antwort.

Schritt 2 - Fall B: Wenn K> len (S):

Wenn S [-1] ≤ 0 ist, gibt es für mehr als eine Woche keinen Wert, daher ist der Maximalwert bis zu einer Woche, dh der Maximalwert von S, die Antwort. Wenn S [-1]> 0 ist, möchte ich so viel wie möglich drehen, aber tatsächlich kann die Punktzahl höher sein, wenn ich eine Runde weniger drehe, also werde ich die Punkte in beiden Fällen berechnen und vergleichen.

Referenz: [Python] ABC175 Erläuterung

Beispielcode

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 = []  #Kumulative Summenliste in Schleife S..jedoch,Der erste Term ist nicht 0, sondern die Punktzahl nach dem ersten Zug.
    #1. Zug
    i = P[s] - 1
    S.append(C[i])
    #Zweiter und nachfolgender Zug.Wiederholen, bis Sie zum Ausgangspunkt zurückkehren.
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])

    ### Step2:Separate Fälle nach der Länge von K und S.,Finden Sie die maximale Punktzahl.
    #Wenn Sie weniger als eine Runde fahren können:
    if K <= len(S):
        score = max(S[:K])
    #Es kann eine Runde überschreiten,Wenn die Punktzahl bei einer Runde der Schleife abnimmt:
    elif S[-1] <= 0:
        score = max(S)
    #Kann eine Woche überschreiten,Und wenn die Punktzahl jede Woche in der Schleife steigt:
    else:
        #Schleife(K // len(S) - 1)Beim Wenden:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        #Schleife(K // len(S))Beim Wenden:
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        #Die größere Punktzahl von Punktzahl1 und Punktzahl2 ist in diesem Fall die maximale Punktzahl.
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)