Courses

Programación dinámica

Patrones en Programación Dinámica

Module: Patrones en Programación Dinámica

Problem

3 /7

Suma de mínimos

Theory Click to read/hide

Si es necesario dividir la matriz en exactamente k subsegmentos, simplemente se agrega el segundo parámetro en la programación dinámica: en cuántos segmentos dividir.
Es decir, ahora consideraremos el siguiente dp:
dp[i][j] es la respuesta para los primeros i elementos, si los dividimos exactamente en j segmentos.
Tenga cuidado con los estados no válidos.

El recálculo de la dinámica es el mismo, pero teniendo en cuenta el segundo parámetro. Es decir, contando dp[i][k] y clasificando a través del borde izquierdo del último subsegmento j, volvemos a calcular dp[i][k] hasta dp[j - 1][k - 1] y el valor del segmento [Ji].

Problem

Se le da una matriz de n enteros. Debe dividirlo en k subsegmentos no vacíos (una secuencia de elementos consecutivos) para que:
1) Cada elemento de la matriz se incluyó exactamente en un subsegmento.
2) Si para cada subsegmento elegimos el número mínimo en él, entonces la suma de todos los mínimos debería ser el máximo posible.

Informe la suma de los mínimos de los valores en los subsegmentos de esta partición.

Entrada:
La primera línea contiene dos números naturales: n (1 <= n <= 500) y k (1 <= k <= n).
La segunda línea contiene n enteros: los elementos de la matriz a_i (1 <= a_i <= 10⁵).< br / >
Salida:
Imprima un número: la respuesta al problema.

Ejemplo:

Explicación:
Una de las particiones adecuadas: [4, 2], [5], [1, 3]. La suma de los mínimos en cada subsegmento es 2 + 5 + 1 = 8.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking