Bolos Bovinos
Las vacas no usan las bolas usuales de bolos cuando van a jugar bolos. A
pesar de eso, cada una toma un número (en el rango ), y se alinean en
un triángulo estándar de bolos como esto:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Entonces las otras vacas recorren el triángulo comenzando desde su parte
superior y se mueven "abajo" hacia una de las dos vacas adyacentes en
diagonal hasta que se llega a la fila "de abajo". Las vacas obtienen
como puntaje la suma de los números de las vacas visitadas en el camino.
La vaca con el más alto puntaje gana esa línea.
Dado un triángulo con
filas, determine la suma más
grande que se pueda obtener.
Entrada
Línea : Un solo entero,
Líneas : La línea
contiene
enteros separados por espacios que representan la fila
del triángulo.
Salida
Línea : La suma más grande que se puede obtener usando las reglas de
recorrido.
Ejemplo de Entrada
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Ejemplo de Salida
30
Detalles de la Salida
7
*
3 8
*
8 1 0
*
2 7 4 4
*
4 5 2 6 5
La suma más grande se puede obtener recorriendo las vacas como se muestra antes.
Comments
pipo eso fue lo que hice pero me rte no se que pasa
el caso # 8 me RTE y todos los demas me dan bien alguien puede decirme que tengo mal
Papo eso es una DP clásica tipo coeficientes binomiales, llevas en cada casilla del array la mejor suma del anterior de arriba y él de la derecha, y luego t quedas con la mayor suma
Es lo mejor del ejercicio, uno de los primeros problemas de DP que estudié.