Cofre de Tesoros
¡Bessie y Bonnie han encontrado un Cofre de Tesoros lleno de maravillosas monedas de oro! Sin embargo, siendo vacas, ellas no pueden caminar simplemente a una tienda y comprar cosas. En vez de esto, ellas deciden divertirse con las monedas.
Las monedas, cada una con algún valor son colocadas en una línea recta. Bessie y Bonnie juegan por turnos, y en cada turno, la jugadora que tiene el turno toma exactamente una moneda o del extremo izquierdo o del extremo derecho de la línea. El juego termina cuando no quedan monedas.
Tanto Bessie como Bonnie quieren obtener tanta ganancia como sea posible para ellas mismas. Bessie va primero. Ayúdela a saber el valor máximo que ella puede ganar, asumiendo que ambas vacas juegan de manera óptima.
Considere un juego en el cual están alineadas cuatro monedas con estos valores:
30 25 10 35
Considere esta secuencia de juego:
Total Total Nueva línea
Jugadora Lado ValorMoneda Bessie Bonnie de monedas
Bessie Derecho 35 35 0 30 25 10
Bonnie Izquierdo 30 35 30 25 10
Bessie Izquierdo 25 60 30 10
Bonnie Derecho 10 60 40 --
Esto es lo mejor que puede hacer Bessie.
Entrada
Línea 1: Un solo entero:
Líneas 2..N+1: La línea i+1 contiene un solo entero:
Ejemplo de Entrada
4
30
25
10
35
Salida
- Línea 1: Un solo entero, el cual el valor total mas grande que Bessie puede ganar si ambas vacas juegan óptimamente.
Ejemplo de Salida
60
Comments