Resolución del problema Lightning Conductor usando tablas dispersas y optimización de decisiones
El problema Lightning Conducter (POI2011) requiere calcular para cada posición i el valor máximo de la expresión:
[\max\left{a_j+\left\lceil\sqrt{|i-j|}\right\rciel\right}-a_i ]
Una solución directa con complejidad (O(n\sqrt{n})) utiliza una tabla de máximos (ST table) para rangos. Dado que (\sqrt{|i-j|}) tiene aproximadaemnte (\sqrt{n}) valore ...
Publicado el 9-16 07:21