UVa 507, Jill Rides Again, da la calificación de cada calle
de una ruta y pide el tramo de calles seguidas con la mayor suma. Si dos
tramos empatan en suma gana el más largo, y si también empatan en largo gana
el que empieza antes. El enunciado está en
https://vjudge.net/problem/UVA-507.
Probar todos los tramos cuesta Θ(n²) sumas; un recorrido basta si en cada
posición se decide si el tramo que viene se alarga o se abre uno nuevo.
1. El arreglo
Ejemplos:
Propio:
Las tres rutas son los casos de prueba del enunciado.
En el último ejemplo varios tramos suman lo mismo.
2. Decida en cada posición
suma e ini
son del tramo que termina en i; mejor, mi y
mf son del mejor tramo visto.
tramo actual
mejor tramo
la posición i
i
A[i]
tramo
suma
ini
mejor
mi..mf
el mejor
Lo que quedó
Para este arreglo, como primera ruta, el programa
de UVa 507 imprime:
La regla de las líneas 4 a 7 dice que una suma negativa
no se arrastra: cualquier tramo que la cargue suma menos que empezar de
nuevo en i. Una suma de cero sí se arrastra, porque no cambia el valor y
alarga el tramo, que es lo que pide el primer desempate. El segundo
desempate sale gratis: entre dos tramos del mismo largo, el recorrido ve
primero el que empieza antes, y la línea 10 solo cambia el mejor si el nuevo es estrictamente más
largo. Dos trampas vienen del enunciado. La calle i une las paradas i e
i + 1, así que el tramo A[mi..mf], contado desde 0, se imprime como las
paradas mi + 1 y mf + 2. Y si la mejor suma no es positiva la ruta no tiene
partes buenas, aunque el recorrido haya encontrado un mejor tramo.
Envío en https://vjudge.net/problem/UVA-507.