题目：

题目在这里

思路:

这题的DP不难， 但不要被题目描述迷惑了

状态转移方程:$f_i = min \{ g_j + (sum_i - sum_j) * sum_j \}$ (用了滚动数组, f是当前处理的， g是上一次得出的)

可以用斜率优化

$g_j + (sum_i - sum_j) * sum_j >= g_k + (sum_i -sum_k) * sum_k$

$g_j - g_k - {sum_j}^2 + {sum_k}^2 >= sum_i * (sum_k - sum_j)$

${g_j - g_k - {sum_j}^2 + {sum_k}^2 \over (sum_k - sum_j)} >= sum_i$

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

inline long long sqr(long long x) { return x * x; }

long long a[N];
long long sum[N];

long long g[N], f[N];
int Q[N], hd, tl;
double calc(int j, int k) { return (double)(g[j]-g[k]+sqr(sum[k])-sqr(sum[j])) / (double)(sum[k]-sum[j]); }

int main()
{   int n, m;
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%lld", &a[i]);
    int tot = 0;
    for(int i=1; i<=n; i++)
        if(a[i] != 0) a[++tot] = a[i];
    n = tot;
    for(int i=1; i<=n; i++)
        sum[i] = sum[i-1] + a[i];
    for(int i=1; i<=m; i++)
    {   hd = tl = 0;
        for(int j=i; j<=n; j++)
        {   while(hd < tl-1 && calc(Q[hd], Q[hd+1]) <= sum[j]) hd++;
            f[j] = g[Q[hd]] + sum[Q[hd]] * (sum[j]-sum[Q[hd]]);
            while(hd < tl-1 && calc(Q[tl-1], j) <= calc(Q[tl-2], Q[tl-1])) tl--;
            Q[tl++] = j;
        }
        for(int j=i; j<=n; j++) swap(f[j], g[j]);
    }
    printf("%lld\n", g[n]);
    return 0;
}