Description
小 (H) 最近迷上了一个分隔序列的游戏。在这个游戏里，小 (H) 需要将一个长度为 (n) 的非负整数序列分割成 (k+1) 个非空的子序列。为了得到 (k+1) 个子序列，小 (H) 需要重复 (k) 次以下的步骤：
-
小 (H) 首先选择一个长度超过 (1) 的序列（一开始小 (H) 只有一个长度为 (n) 的序列——也就是一开始得到的整个序列）；
-
选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后，小 (H) 将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小 (H) 希望选择一种最佳的分割方式，使得 (k) 轮之后，小 (H) 的总得分最大。
Input
输入第一行包含两个整数 (n,k（k+1le n）)。
第二行包含 (n) 个非负整数 (a_1,a_2,...,a_n(0le a_i le 10^4))，表示一开始小 (H) 得到的序列。
Output
输出第一行包含一个整数，为小 (H) 可以得到的最大分数。
Sample Input
7 3
4 1 3 4 0 2 3
Sample Output
108
Solution
- (dp[i] = max(dp[j] + (s_i - s_j) imes s_j))
设
- (j < k) ， 从 (k) 转移由于 从 (j) 。
那么
- (dp[j] + (s_i - s_j) imes s_j < dp[k] + (s_i - s_k) imes s_k)
化简一下
- (frac {(dp[j] - s_j^2) - (dp[k] - s_k^2)} {s_k - s_j} < s_i)