DP/四边形不等式
要求将一个可重集S分成M个子集，求子集的极差的平方和最小是多少……
首先我们先将这N个数排序，容易想到每个自己都对应着这个有序数组中的一段……而不会是互相穿插着= =因为交换一下明显可以减小极差
然后……直接四边形不等式上吧……这应该不用证明了吧？
MLE了一次：这次的w函数不能再开数组去存了……会爆的，直接算就行了= =反正是知道下标直接就能乘出来。
数据比较弱，我没开long long保存中间结果居然也没爆……（只保证最后结果不会爆int，没说DP过程中不会……）
//HDOJ 3480
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
#define SHOW_MEMORY(x) cout<<sizeof(x)/(1024.0)<<"KB"<<endl
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,INF=~0u>>;
const double eps=1e-;
/*******************template********************/
int dp[][N],n,m,a[N],s[][N],ans;
void work(){
n=getint(); m=getint();
F(i,,n) a[i]=getint();
sort(a+,a+n+);
F(i,,m) F(j,,n) dp[i][j]=INF;
F(i,,n){
dp[][i]=(a[i]-a[])*(a[i]-a[]);
s[][i]=;
}
F(i,,m){
s[i][n+]=n;
D(j,n,i)
F(k,s[i-][j],s[i][j+])
if(dp[i-][k]+(a[j]-a[k+])*(a[j]-a[k+])<dp[i][j]){
s[i][j]=k;
dp[i][j]=dp[i-][k]+(a[j]-a[k+])*(a[j]-a[k+]);
}
}
ans=dp[m][n];
}
int main(){
int T=getint();
F(i,,T){
work();
printf("Case %d: %d\n",i,ans);
}
return ;
}