比较明显的斜率优化DP，省选时因为时间太紧张和斜率DP写得不熟等原因只写了60分的暴力DP，其实当时完全可以对拍来检验标算的正确，但是我当时too naive～
很快打完了，调了将近一晚上QAQ，因为脑残地把两个变量名打反了。错在这上面却只有一组WA，所以总是在想一些奇葩的错误(数组越界什么的，int没有强转long long←几天前做数论和FFT留下的后遗症)，没有先认真地静态查错。以后一定要认真仔细，杜绝手残的行为！比赛时绝不会有这么长的调试时间，手残一次就会滚粗了QuQ
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
int getint() {
long long k = 0; int fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
}
long long sqr(int x) {return 1LL * x * x;}
long long f[3003][3003];
int n, m, a[3003], sum[3003], q[3003], head, tail, h, t;
bool cmpdown(int j, int x, int y, int i) {
return (f[x][j - 1] - f[y][j - 1] + sqr(sum[x]) - sqr(sum[y])) * (sum[y] - sum[i])
> (f[y][j - 1] - f[i][j - 1] + sqr(sum[y]) - sqr(sum[i])) * (sum[x] - sum[y]);
}
int main() {
read(n); read(m);
for(int i = 1; i <= n; ++i)
read(a[i]);
sum[0] = 0;
for(int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + a[i];
for(int i = 1; i <= n; ++i)
f[i][1] = sqr(sum[i]);
for(int j = 2; j <= m; ++j) {
head = 1; tail = 0;
for(int i = 1; i <= n; ++i) {
while (head < tail && cmpdown(j, q[tail - 1], q[tail], i))
--tail;
q[++tail] = i;
while (head < tail
&& f[q[head]][j - 1] - f[q[head + 1]][j - 1] + sqr(sum[q[head]]) - sqr(sum[q[head + 1]])
> 2 * sum[i] * (sum[q[head]] - sum[q[head + 1]]))
++head;
f[i][j] = f[q[head]][j - 1] + sqr(sum[i] - sum[q[head]]);
}
}
long long ans = f[n][m] * m - sqr(sum[n]);
printf("%I64d\n", ans);
return 0;
}
没了TwT