Editorial for Vacaciones
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Este problema se puede modelar como un grafo, en el cual los nodos son del tipo , ej:
,
o
; que significa que acabó en la posición
, y el último elemento igual a
. Las aristas serían las siguientes:
Para cada de
a
:
a
a
a
Con esto el problema queda a buscar el máximo camindo en un grafo dirigido acíclico, que se puede hacer manteniendo como el máximo camino que termine en
, que se puede calcular como el máximo
para todo
hijo de
, más el costo del nodo
.
Comments