Der Titel sagt Python, aber ich kann es nicht rechtzeitig schaffen, ohne PyPy zu verwenden. ** Es ist auf jeden Fall ein Titelbetrug. Ich bin dir wirklich dankbar. ** ** ** ~~ Uruse, benutze PyPy ~~
** Gedanken ** Ein ähnliches Problem trat kürzlich in ABC auf. Der große Unterschied zwischen der letzten Frage und dieser Frage besteht darin, ob die Form des Diagramms 6 oder ein Kreis ist. Da die vergangene Frage die Form 6 hatte, war es notwendig, den Zeitpunkt des Eintritts in den Zyklus aufzuzeichnen. Das Problem ist diesmal jedoch, dass die Form des Diagramms ein Kreis ist.
Warum ein gegebener Graph einen Zyklus hat (geschlossen): Wenn der angegebene Graph keine Zyklen hat, wird der Graph zu einem Baum, und es gibt Knoten, die keine untergeordneten Knoten haben (Knoten, die kein Ziel haben). Da $ P $ jedoch eine Folge von $ N $ gemäß der Bedingung ist, gibt es keinen untergeordneten Knoten ($ P_i $ ist leer). Der gegebene Graph hat also einen Zyklus
Warum die angegebene Diagrammform ein Kreis ist: Angenommen, die Form des angegebenen Diagramms ist kein Kreis. Die obige Grafik hat einen Zyklus. Der Startpunkt eines nicht kreisförmigen Zyklus ist mit zwei Knoten verbunden (das Ziel ist das gleiche ⇔ $ P_i = P_j (i \ neq j) $ existiert). Entsprechend der Bedingung liegen die Elemente von $ P $ jedoch in der Größenordnung von $ N $, sodass die Elemente von $ P $ nicht zusammengesetzt werden. Da kein Punkt mit zwei oder mehr Punkten verbunden ist, ist der angegebene Graph ein Kreis.
Bei der Untersuchung des Zyklus denke ich, dass es einfach ist, die gesuchte Liste zu erstellen und zu aktualisieren, die in DFS usw. verwendet wird.
Alles was Sie tun müssen, ist die Partitur zu verarbeiten. Zuerst dachte ich, ich sollte es aktualisieren (wenn ich so viel wie möglich herumgehe + wenn ich die maximale Masse mit der verbleibenden Anzahl von Malen bewege, wenn es nur eine Runde gibt). Ich habe es ungefähr 2 Stunden lang geschmolzen, ohne diese Lüge zu bemerken. Dies schlägt im folgenden Testfall fehl.
3 6
2 3 1
5 5 -9
Der Graph schleift 1 → 2 → 3 → 1. Die erste Idee ist 3 → 2 → 1 und die Antwort ist 10. Dies ist falsch und die richtige Antwort ist 11. Die richtige Antwort für diesen Fall lautet 3 → 1 → 2 → 3 → 1 → 2. Die erste Idee ist, zwischen 2 Runden + 1 Quadrat oder 2 Quadraten zu wählen. Im Fall von 2 Runden + 1 Quadrat ist es 7 und im Fall von 2 Quadraten ist es 10 wie oben. Die richtige Antwort ist 1 Runde + 2 Felder.
Daher ist das richtige Update (wenn Sie so oft wie möglich herumlaufen + die maximale Anzahl von Quadraten, wenn Sie nur eine Runde machen, ** Sie gehen so oft wie möglich herum + 1 + die maximale Anzahl von Bewegungen ** Wann). Alles was Sie tun müssen, ist es zu implementieren.
Der Anfangswert von ans ist -inf, da 0 Züge die Antwort sind, wenn die Antwort negativ ist.
n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = -float('inf')
for i in range(n):
score = []
check = [0] * n
now = i
cycle = 0
for _ in range(k):
go = p[now] - 1
if check[go] == 1:
break
now = go
if len(score) == 0:
score.append(c[now])
else:
score.append(score[-1] + c[now])
check[now] = 1
cycle += 1
t = k // cycle
m = k % cycle
sum_cycle = score[-1]
if m == 0:
ans = max(sum_cycle * t, sum_cycle * (t - 1) + max(score), max(score), ans)
else:
ans = max(sum_cycle * t + max(score[:m]), sum_cycle * (t - 1) + max(score), max(score), ans)
print(ans)
Vielen Dank an Ryuki für das Teilen des Testfalls. Es war ein lustiges Problem. Wir sehen uns wieder, gute Nacht.
3 7
— Ryuki (@e145755) August 16, 2020
2 3 1
5 5 -9
Recommended Posts