1 /*
2 * File: Toj 3305.cpp
3 * Author: GongZhi
4 * Problem: 动态规划，四边形不等式优化
5 * Created on 2009年7月27日, 上午12:00
6 */
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16
17 /*
18 *
19 */
20 #define MAXN 1100
21 long long a[MAXN], sum1[MAXN], sum2[MAXN], f[MAXN][MAXN], w[MAXN][MAXN], p[MAXN][MAXN];
22
23 int main() {
24 int n, m, i, j, t, k;
25 while (scanf("%d%d", &n, &m), n) {
26 m++;
27 for (i = 1; i <= n; i++)scanf("%d", &a[i]);
28 sum1[0] = 0;
29 sum2[0] = 0;
30 for (i = 1; i <= n; i++)sum1[i] = sum1[i - 1] + a[i];
31 for (i = 1; i <= n; i++)sum2[i] = sum2[i - 1] + a[i] * a[i];
32 for (i = 1; i <= n; i++)
33 for (j = 1; j <= n; j++)w[i][j] = ((sum1[j] - sum1[i - 1])*(sum1[j] - sum1[i - 1])-(sum2[j] - sum2[i - 1])) / 2;
34 for (i = 1; i <= n; i++) {
35 f[1][i] = w[1][i];
36 p[1][i] = 1;
37 }
38 for (i = 2; i <= m; i++) {
39 j = n;
40 f[i][j] = 100000000000000ll;
41 for (k = p[i - 1][j]; k <= j - 1; k++)
42 if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
43 f[i][j] = f[i - 1][k] + w[k + 1][j];
44 p[i][j] = k;
45 }
46 for (j = n - 1; j >= 1; j--) {
47 f[i][j] = 100000000000000ll;
48 for (k = p[i - 1][j]; k <= p[i][j + 1]; k++)
49 if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
50 f[i][j] = f[i - 1][k] + w[k + 1][j];
51 p[i][j] = k;
52 }
53 }
54 }
55 printf("%d\n", f[m][n]);
56 }
57 return 0;
58 }
59
60