Module: Patterns in Dynamic Programming


Problem

3 /7


Sum of lows

Theory Click to read/hide

If it is necessary to divide the array into exactly k subsegments, then the second parameter is simply added in dynamic programming - how many segments to split into.
That is, now we will consider the following dp:
dp[i][j] is the answer for the first i elements, if we split them into exactly j segments.
Watch out for invalid states.

The recalculation of the dynamics is the same, but taking into account the second parameter. That is, counting dp[i][k] and sorting through the left border of the last subsegment j, we recalculate dp[i][k] through dp[j - 1][k - 1] and the value of the segment [j;i].

Problem

You are given an array of n integers. You need to divide it into k non-empty subsegments (a sequence of consecutive elements) so that:
1) Each element of the array was included in exactly one subsegment.
2) If for each subsegment we choose the minimum number in it, then the sum of all minima should be the maximum possible.

Report the sum of the minima of the values ​​in the subsegments of this partition.

Input:
The first line contains two natural numbers - n (1 <= n <= 500) and k (1 <= k <= n).
The second line contains n integers - the elements of the array ai (1 <= ai <= 105).

Output:
Print one number - the answer to the problem.

Example:
 
Input Output
5 3
4 2 5 1 3 		8

Explanation:
One of the suitable partitions: [4, 2], [5], [1, 3]. The sum of the minima in each sub-segment is 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!