<h2>题意</h2>
有长度为 n 的序列，定义一个集合的代价是$(MAX-MIN)^2$，要求你找出 m 个集合，在满足下面图片的限制的情况下，使得总代价最小。
多组数据，每组数据 $n \leq 10^4,m \leq 5 \times 10^3$，保证答案在 int 范围内。
<h2>题解</h2>
观察题目 发现让你选取 M 个集合使得代价最小。
首先一个观察是，取得代价最小的方案一定是按照排序后按顺序取的，并且这些集合两两不交。
然后我们考虑排序后进行 dp：记前 i 段选了 j 个数的最小代价是 $f_{i,j}$，暴力转移就是枚举最后选择的一段区间，暴力转移方程：
$$f_{i,j} = min \{f_{i-1,k} + (a_i - a_{k+1})^2 \}$$
这样复杂度是 $O(n^2m)$ 显然过不去。于是我们来考虑进行斜率优化。
首先发现当前转移只与第二维上一次的状态有关，可以考虑滚动数组，即记 $g = f_{i-1}$，那么我们化简递推式，可以得到
$$f_{i} = min\{g_{k}+(a_i-a_{k+1})^2\}$$
套路地设如果 $j < k$ 且从 $j$ 转移更优，则有式子：
$$g_{j} +(a_i - a_{j+1})^2 < g_k + (a_i - a_{k+1})^2$$
化简一下：
$g_{j} +(a_i - a_{j+1})^2 < g_k + (a_i - a_{k+1})^2$
$\Rightarrow g_j+a_{j+1}^2-2a_ia_{j+1} < g_k + a_{k+1}^2 - 2a_ia_{k+1}$
$\Rightarrow g_j+a_{j+1}^2 - g_k-a_{k+1}^2 < 2a_i(a_{j+1}-a_{k+1})$
不妨令 $F_i = g_i-a_{i+1}^2$
$\Rightarrow F_j-F_k < 2a_i(a_{j+1}-a_{k+1})$
$\Rightarrow \frac{F_j-F_k}{a_{j+1}-a_{k+1}} > 2a_i$
当 $j$ 不比 $k$ 优时，满足 $\frac{F_j-F_k}{a_{j+1}-a_{k+1}} \leq 2a_i$，也可以写成 $\frac{F_k-F_j}{a_{k+1}-a_{j+1}} \leq 2a_i$。
然后直接上斜率优化就好了。具体见代码。
<h1>代码</h1>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 10000+5;
int f2,n,m,aa[MAXN],now;
#define X(i) (aa[i+1])
#define Y(i) (fnow^1+aa[i+1]*aa[i+1])
inline bool chkhead(int a,int b,int c){
return (Y(b)-Y(a)) <= 2(X(b)-X(a))aa[c];
}
inline bool chktail(int a,int b,int c){
return (Y(b)-Y(a))(X(c)-X(b)) >= (Y(c)-Y(b))(X(b)-X(a));
}
int q[MAXN],head,tail;
inline int calc(int i,int j){
return fnow^1 + (aa[j+1]-aa[i])*(aa[j+1]-aa[i]);
}
inline void init(){
CLR(q,0);head = tail = 0;CLR(f,0);CLR(aa,0);now = 0;
}
inline void Solve(int times){
scanf("%lld%lld",&n,&m);
FOR(i,1,n) scanf("%lld",aa+i);
std::sort(aa+1,aa+n+1);
now = 0;FOR(i,1,n) fnow = (aa[i]-aa[1])*(aa[i]-aa[1]);
FOR(i,2,m){
now ^= 1;q[head = tail = 0] = 0;
CLR(f[now],0);
FOR(j,1,n){
while(head < tail && chkhead(q[head],q[head+1],j)) head++;
fnow = calc(j,q[head]);
while(head < tail && chktail(q[tail-1],q[tail],j)) tail--;
q[++tail] = j;
}
}
printf("Case %lld: %lldn",times,fnow);
}
signed main(){
int T;scanf("%lld",&T);
FOR(i,1,T) Solve(i);
return 0;
}
