题意：给你n个数，然后让你分成m个集合，每个集合有一个值（最大值减最小值，然后平方），求整个集合的可能最小值。

思路：因为每个集合里的值只和最大和最小值有关，所以很容易想到先排序，然后用DP可求得解，状态转移方程dp[i][j] = min(dp[i][j] , dp[k][j - 1] + (a[i] - a[k + 1]) ^ 2)，j表示数组的下标，i表示集合数，dp为最小值，但是因为n为10000，m为5000，这个复杂度肯定会超时，所以可以用斜率或四边形优化来减小复杂度，式子就不证明了，这里直接引用，另外贴上四边形优化的一个链接，讲的挺详细的点击打开链接

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 10010

#define ll long long

using namespace std;

ll a[MAXN];

ll dp[MAXN][MAXN];

int N, M;

ll q[MAXN];

ll head, tail;

void init()

{

    for (int i = 1; i <= N; i++)

        dp[1][i] = (a[i] - a[1])*(a[i] - a[1]);

}

void solve()

{

    for(int i=2;i<= M;i++)

    {

        head=tail=0;

        q[tail++]=i-1;

        for(int j = i;j <= N;j++)

        {

            while(head+1<tail)

            {

                int p1=q[head];

                int p2=q[head + 1];

                int x1=a[p1 + 1];

                int x2=a[p2 + 1];

                int y1=dp[i - 1][p1] + x1*x1;

                int y2=dp[i - 1][p2] + x2*x2;

                if((y2-y1)<= 2*a[j]*(x2-x1))head++;

                else break;

            }

            int k=q[head];

            dp[i][j]=dp[i-1][k]+(a[j]-a[k+1])*(a[j]-a[k+1]);

            while(head+1<tail)

            {

                int p1=q[tail-2];

                int p2=q[tail-1];

                int p3=j;

                int x1=a[p1+1];

                int x2=a[p2+1];

                int x3=a[p3+1];

                int y1=dp[i-1][p1]+x1*x1;

                int y2=dp[i-1][p2]+x2*x2;

                int y3=dp[i-1][j]+x3*x3;

                if ((y3-y2)*(x2-x1)<=(y2-y1)*(x3-x2))tail--;

                else break;

            }

            q[tail++]=j;

        }

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    int k=0;

    while(T--)

    {

        k++;

        scanf("%d%d",&N,&M);

        for (int i = 1; i <= N; i++)

            scanf("%d", &a[i]);

        sort(a+1,a+N+1);

        init();

        solve();

        printf("Case %d: %d\n",k,dp[M][N]);

    }

    return 0;

}