简单来说就是用了一个（一开始不知道对不对的）决策单调性，然后每次从两个旁边的决策点里选个最大的开扫，然后就……水过去了……

code:

#include <cstdio>
typedef long long ll;
const int N = 3007;
const ll INF = 0x3fffffffffffffff;
inline ll min(ll a, ll b) {
    return a < b ? a : b;
}
inline ll max(ll a, ll b) {
    return a > b ? a : b;
}

ll f[N][N];
int g[N][N];
ll sum[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", sum + i);
        sum[i] += sum[i - 1];
    }
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            f[i][j] = INF;
        }
    }
    f[0][0] = 0;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = max(g[i][j - 1], g[i - 1][j]); k <= j; k++) {
                if (f[i][j] > f[i - 1][k] + (sum[j] - sum[k]) * (sum[j] - sum[k])) {
                    f[i][j] = f[i - 1][k] + (sum[j] - sum[k]) * (sum[j] - sum[k]);
                    g[i][j] = k;
                }
                //f[i][j] = min(f[i][j], f[i - 1][k] + (sum[j] - sum[k]) * (sum[j] - sum[k]));
            }
        }
    }
    printf("%lld", m * f[m][n] - sum[n] * sum[n]);
    return 0;
}

（正解什么的有在写了.jpg）