题目链接：
题意：
给你一个有n个数的集合S，现在让你选出m个子集合，使这m个子集合并起来为S，并且每个集合的(max-min)2 之和要最小。
题解：
运用贪心的思想，肯定首先将全部的数排好序，然后设dp[i][j]表示前j个数分为i个集合的最优解。
则有dp[i][j]=min{dp[i-1][k]+(a[j]-a[k+1])2}(0<k<j)。
这样写出来是三层for的dp，考虑用斜率优化降维。
假设l<k<j,对于dp[i][j]，k到j为一个集合比l到j为一个集合更优。
则有：dp[i-1][k]+(a[j]-a[k+1])2<=dp[i-1][l]+(a[j]-a[l+1])2。
整理得 dp[i-1][k]+a[k+1]2 -dp[i-1][l]+a[l+1]2 /a[k+1]-a[l-1]<=2*a[j]。
然后就是y1-y2/x1-x2<=L的斜率形式了。
1 #include2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int N=10007; 6 7 int t,n,m,dp[2][N],Q[N],a[N],ic; 8 9 int getx(int k,int l){ return a[k+1]-a[l+1];}10 int gety(int i,int k,int l){ return dp[i][k]+a[k+1]*a[k+1]-dp[i][l]-a[l+1]*a[l+1];}11 int check(int i,int j,int k,int l){ return gety(i,j,k)*getx(k,l)<=gety(i,k,l)*getx(j,k);}12 13 int main()14 {15 scanf("%d",&t);16 while(t--)17 {18 scanf("%d%d",&n,&m);19 F(i,1,n)scanf("%d",a+i);20 sort(a+1,a+1+n);21 F(i,1,n)dp[0][i]=(a[i]-a[1])*(a[i]-a[1]);22 F(i,2,m)23 {24 int now=0,head=1,tail=0;25 Q[++tail]=i-1;26 F(j,i,n)27 {28 while(head
