Module: 动态规划中的模式


Problem

3 /7


低点总和

Theory Click to read/hide

如果需要把数组恰好分成k个子段，那么在动态规划中只需要加上第二个参数——分成多少段。
即，现在我们将考虑以下 dp：
dp[i][j] 是前 i 个元素的答案，如果我们将它们分成恰好 j 个部分。
注意无效状态。

动力学的重新计算是相同的，但考虑了第二个参数。即统计dp[i][k]并通过最后一个子段j的左边界进行排序，我们通过dp[j - 1][k - 1]和段的值重新计算dp[i][k] [j;i]。

Problem

给定一个包含 n 个整数的数组。你需要把它分成k个非空子段（一系列连续的元素）使得：
1) 数组的每个元素恰好包含在一个子段中。
2) 如果对于每个子段我们选择其中的最小数，那么所有最小值的总和应该是最大可能的。

报告此分区的子段中值的最小值之和。

输入：
第一行包含两个自然数——n（1 <= n <= 500）和k（1 <= k <= n）。
第二行包含 n 个整数——数组 ai 的元素 (1 <= ai <= 105).< br/>
输出：
打印一个数字 - 问题的答案。

示例：
  <正文>
解释：
合适的分区之一：[4, 2], [5], [1, 3]。每个子段中的最小值之和为 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!

输入 输出
5 3
4 2 5 1 3 		8