RT,教练自己的题目。

在修建完新路后，小羊们总算可以安心入学了。今年是羊年，新入学的小羊特别多。老师们打算将N只小羊分成M个班级，每个班至少有1只羊。 如何分班成了老师们最头疼的事情，因为开学典礼上，村长就要看到小羊们列队的情况。每个班的小羊都排成一排，站在草场上。村长希望队列中羊的高度尽可能整齐，村长对队列的不整齐度有自己的要求。 例如队列中共有t只羊，高度依次为A1，A2……，At。那么不整齐度为：(|A1-A2|+|A2-A3|+……+|At-1-At|)2。即相邻两只羊高度差之和的平方。 而总体的不整齐度，就是各班不整齐度之和。 现在，请你帮助老师们设计一下，如何分班，如何列队，才能使M个班级的不整齐度之和最小。

思路：DP

$f[i][j] = \min_{0<k<i} \{ f[k][j-1] + (a[i]-a[k+1])^2\}$

进行斜率优化（十字相乘避免精度问题，滚动数组空间优化）

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
long long head, tail, n, m, a[10005], f[10005][3], que[1005][10005];
int main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    sort(a+1, a+1+n);
    f[0][1] = 1e10;
    for(int i = 1; i <= n; i++)
        f[i][1] = (a[i] - a[1])*(a[i] - a[1]);
    int now = 0, last = 1;
    for(int j = 2; j <= m; j++){
        head = 1; tail = 1;
        que[j][tail] = j-1;
        for(int i = 0; i < j; i++) f[i][now] = 1e10;
        for(int i = j; i <= n; i++){
            while(head < tail && 
            f[que[j][head+1]][last]-f[que[j][head]][last] + a[que[j][head+1]+1]*a[que[j][head+1]+1]-a[que[j][head]+1]*a[que[j][head]+1]
            < a[i]*2*(a[que[j][head+1]+1]-a[que[j][head]+1])) 
                head++;
            f[i][now] = f[que[j][head]][last] + (a[i]-a[que[j][head]+1]) * (a[i]-a[que[j][head]+1]);
            while(head < tail && 
            (f[que[j][tail-1]][last]-f[que[j][tail]][last]+a[que[j][tail-1]+1]*a[que[j][tail-1]+1]-a[que[j][tail]+1]*a[que[j][tail]+1])
            *2*(a[que[j][tail]+1]-a[i+1])
            < (f[que[j][tail]][last]-f[i][last]+a[que[j][tail]+1]*a[que[j][tail]+1]-a[i+1]*a[i+1])
            *2*(a[i+1]-a[que[j][tail]+1]))
                tail --;
            que[j][++tail] = i;
        }
        last = 1 - last;
        now = 1 - now;
    }
/*
    for(int i = 0; i <= n; i++){
            printf("%12d", f[i][last]);
        printf("\n");
    }
*/
    printf("%lld", f[n][last]);
    return 0;
}

然而$\color{red}WA$100%