Slimes
Hay slimes alineados en una fila. Inicialmente, el slime i-ésimo de la izquierda tiene un tamaño de
.
Taro está tratando de combinar todos los slimes en un slime más grande. Realizará la siguiente operación repetidamente hasta que solo quede un slime:
- Elija dos slimes adyacentes y combínelos en un nuevo slime. El nuevo slime tiene un tamaño de
+
, donde
. La relación posicional de los slimes no cambia mientras se combinan los slimes.
Encuentre el costo total mínimo posible incurrido.
Restricciones
- Todos los valores de la entrada son números enteros.
- \(2\leN\le400\)
- \(1\leai\le10^9\)
Entrada:
La entrada contiene a seguido por
números enteros, el i-ésimo de ellos es
.
Salida:
Imprima el costo total mínimo posible.
Entrada de muestra 1:
4
10 20 30 40Salida de muestra 1:
190Taro debe hacer lo siguiente:
\((10, 20, 30, 40) → (30, 30, 40)\)
\((30, 30, 40) → (60, 40)\)
\((60, 40) → (100)\)
Entrada de muestra 2:
5
10 10 10 10 10Salida de muestra 2:
120Taro debería hacer, por ejemplo, lo siguiente:
\((10, 10, 10, 10, 10) → (20, 10, 10, 10)\)
\((20, 10, 10, 10) → (20, 20, 10)\)
\((20, 20, 10) → (20, 30)\)
\((20, 30) → (50)\)
Entrada de muestra 3:
3
1000000000 1000000000 1000000000Salida de muestra 3:
5000000000Es posible que la respuesta no se ajuste a un tipo entero de bits.
Comments
Alguien puede explicarme el problema? No entiendo nada. Por qué en el ejemplo 2, por ejemplo, si la entrada es
5
10 10 10 10 10
Te dicen que la salida es 120 y debajo te dan una explicación con la que llegan al resultado 50 (el mismo que según yo debería ser el correcto despues de leer la descripción del problema)
Por alguien que me pueda ayudar!!!
Lo que pasa es que deben mostrar el costo minimo para juntar todos los slimes pero cuando sumas un slime con otro el costo aumenta en la suma de ambos,no en el que le aumentas.
No entiendo
por ejemplo,en el segundo ejemplo primero juntan el 1ro con el 2do por lo que el costo aumenta en la suma de sus valores osea 10+10;luego el 3ro con el 4to el costo tambien aumentaria en 10+10;luego el 2do con el 3ro y el costo aumenta en 20+10;y asi consecutivamente. Recuerda que al juntar un slime con otros estos se convierten en uno solo(la suma de sus valores).
no me da to los putos alguien me puede decir como encontrar la solución.por donde tengo q cojer , por el camino red o por el camino blue
creo q deverias d estuiar un poco mas DP
No entiendo
ayudaaaaaa!