Hola necesito ayuda con este problema de la CIIC 2018 es el problema C: https://omegaup.com/arena/problem/CIIC2018-Juego/
1 me gusta
Hola!
La primera clave está en que hay n+1 operaciones posibles para hacer, según dónde comienza el rango. Además, se puede observar que el orden de las operaciones que se haga no cambia el resultado final obtenido, y que hacer la misma operación dos veces seguidas se cancela, por lo tanto solamente importa para cada una de estas n+1 operaciones posibles si se realiza o no se realiza, o sea que son como botones que se pueden activar o no, y hay que elegir cuáles activar para maximizar la suma.
La segunda clave está en que si en lugar de poder “apretar o desapretar” los n+1 botones individualmente a gusto, nos imaginamos que nos dieran la operación cambiada de “apretar o desapretar” (cambiar el estado) de dos botones consecutivos, podemos generar prácticamente cualquier configuración de botones igualmente: si vamos de comienzo a final, podemos en cada pasa apretar ese botón (y el siguiente) o no, según convenga para el estado que queremos generar. El único botón que no podemos controlar de esta manera es el último, que queda determinado por los anteriores. Pero entonces si agregamos la operación de “vale tocar el último botón por separado”, nos aseguramos cubrir todas las posibilidades sin perder opciones.
Entonces, probamos las dos opciones posibles de si arrancar con el arreglo original, o si primero cambiar el signo de los n últimos (operación que corresponde al último botón), y al final tomaremos la mejor de las dos opciones. Hecho esto, tenemos que considerar lo mejor que es posible dado que solamente hacemos pares de operaciones consecutivas.
¿Por qué es mejor esto? Porque hacer dos operaciones consecutivas tiene una propiedad muy conveniente: todos los del medio se cancelan porque son invertidos dos veces. Así que la operación lo único que hace es, para un i a elección, cambiar el signo del i y del i+n. Como justo n es la mitad del total, esto los pone en parejitas y la operación posible es cambiar el signo a la parejita o no, es decir, ahora las parejitas son completamente independientes entre sí. Esto permite que golosamente por cada parejita tomamos la opción que dé suma mayor, y eso dará el máximo total.
En pseudocódigo sería: rta = max(calcular(original), calcular(original con los últimos n negados))
Y a su vez calcular(v) sería calcular la suma de max(v[i] + v[i+n], -v[i] - v[i+n]) para i variando entre 0 y n-1 inclusive.
1 me gusta