Module: Modèles en programmation dynamique


Problem

3 /7


Somme des bas

Theory Click to read/hide

S'il est nécessaire de diviser le tableau en exactement k sous-segments, le deuxième paramètre est simplement ajouté dans la programmation dynamique - le nombre de segments à diviser.
Autrement dit, nous allons maintenant considérer le dp suivant :
dp[i][j] est la réponse pour les i premiers éléments, si nous les divisons en exactement j segments.
Faites attention aux états invalides.

Le recalcul de la dynamique est le même, mais en tenant compte du second paramètre. Autrement dit, en comptant dp[i][k] et en triant par la bordure gauche du dernier sous-segment j, nous recalculons dp[i][k] à dp[j - 1][k - 1] et la valeur du segment [j;i].

Problem

On vous donne un tableau de n entiers. Vous devez le diviser en k sous-segments non vides (une séquence d'éléments consécutifs) de sorte que :
1) Chaque élément du tableau était inclus dans exactement un sous-segment.
2) Si pour chaque sous-segment nous choisissons le nombre minimum qu'il contient, alors la somme de tous les minima devrait être le maximum possible.

Indiquez la somme des minima des valeurs dans les sous-segments de cette partition.

Saisie :
La première ligne contient deux nombres naturels - n (1 <= n <= 500) et k (1 <= k <= n).
La deuxième ligne contient n entiers - les éléments du tableau ai (1 <= ai <= 105).< br / >
Sortie :
Imprimez un numéro - la réponse au problème.

Exemple :
 
Entrée Sortie
5 3
4 2 5 1 3 		8

Explication :
Une des partitions appropriées : [4, 2], [5], [1, 3]. La somme des minima dans chaque sous-segment est 2 + 5 + 1 = 8.

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

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!