Le titre dit Python, mais je ne peux pas arriver à temps sans utiliser PyPy. ** C'est une arnaque au titre par tous les moyens. Je vous en suis vraiment reconnaissant. ** ** ~~ Uruse, utilisez PyPy ~~
** Pensées ** Un problème similaire est apparu récemment dans ABC. La grande différence entre la question précédente et cette question est de savoir si la forme du graphique est comme 6 ou un cercle. Puisque la question précédente était comme 6, il était nécessaire d'enregistrer le moment de l'entrée dans le cycle. Cependant, le problème cette fois est que la forme du graphique est un cercle.
Pourquoi un graphe donné a un cycle (fermé): Si un graphe donné n'a pas de cycles, alors le graphe devient un arbre et il y a des nœuds qui n'ont pas de nœuds enfants (des nœuds qui n'ont pas de destination). Cependant, puisque $ P $ est une séquence de $ N $ selon la condition, il n'y a pas de nœud enfant ($ P_i $ est vide). Donc le graphique donné a un cycle
Pourquoi la forme de graphique donnée est un cercle: Supposons que la forme du graphique donné ne soit pas un cercle. Le graphique ci-dessus a un cycle. Le point de départ d'un cycle non circulaire est relié à deux nœuds (la destination est la même ⇔ $ P_i = P_j (i \ neq j) $ existe). Cependant, selon la condition, les éléments de $ P $ sont de l'ordre de $ N $, donc les éléments de $ P $ ne sont pas composés. Par conséquent, comme il n'y a pas de point connecté à deux points ou plus, le graphique donné est un cercle.
Lors de l'examen du cycle, je pense qu'il est facile de créer et de mettre à jour la liste recherchée qui est utilisée dans DFS, etc.
Tout ce que vous avez à faire est de traiter le score. Au début, j'ai pensé que je devais le mettre à jour avec (quand je fais le tour autant que je peux + quand je déplace la masse maximale avec le nombre de fois restant, quand il n'y a qu'un tour). Je l'ai fait fondre pendant environ 2 heures sans remarquer ce mensonge. Cela échouera dans le cas de test suivant.
3 6
2 3 1
5 5 -9
Le graphique boucle 1 → 2 → 3 → 1. La première idée est 3 → 2 → 1 et la réponse est 10. C'est faux et la bonne réponse est 11. La bonne réponse dans ce cas est 3 → 1 → 2 → 3 → 1 → 2. La première idée est de choisir entre 2 tours + 1 carré ou 2 carrés. Dans le cas de 2 tours + 1 carré, ce sera 7, et dans le cas de 2 carrés, ce sera 10 comme ci-dessus. La bonne réponse est 1 tour + 2 carrés.
Par conséquent, la mise à jour correcte est (lorsque vous faites le tour autant de fois que vous le pouvez + le nombre maximum de mouvements de carrés, lorsque vous ne faites qu'un tour, ** vous faites le tour autant de fois que vous le pouvez + 1 + le nombre maximum de fois que vous vous déplacez ** Quand). Tout ce que vous avez à faire est de le mettre en œuvre.
La valeur initiale de ans est -inf car 0 déplacement sera la réponse lorsque la réponse est négative.
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)
Merci à Ryuki pour le partage du cas de test. C'était un problème amusant. A bientôt, bonne nuit.
3 7
— Ryuki (@e145755) August 16, 2020
2 3 1
5 5 -9
Recommended Posts