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é.