题目大意：将n个数分成m组，将每组的最大值与最小值的平方差加起来，求最小和。

题目分析：先对数排序。定义状态dp(i,j)表示前 j 个数分成 i 组得到的最小和，则状态转移方程为dp(i,j)=min(dp(i,k-1)+w(k,j))，其中w(i,j)=(a[i]-s[j])*(a[i]-a[j])。很显然，dp(i,j)满足凸四边形不等式。

 

代码如下：

# include
     
      # include
      
       # include
       
        # include
        
         using namespace std;const int INF=1<<30;int dp[10005][505];int K[10005][505];int a[10005];int n,m;void read(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i)        scanf("%d",a+i);}int solve(){    sort(a+1,a+n+1);    for(int i=1;i<=n;++i){        dp[1][i]=(a[i]-a[1])*(a[i]-a[1]);        K[1][i]=0;        if(i<=m){            dp[i][i]=0;            K[i][i]=i;        }    }    for(int i=2;i<=m;++i){        K[i][n+1]=n;        for(int j=n;j>=i;--j){            dp[i][j]=INF;            for(int k=K[i-1][j];k<=K[i][j+1];++k){                if(dp[i][j]>dp[i-1][k-1]+(a[j]-a[k])*(a[j]-a[k])){                    dp[i][j]=dp[i-1][k-1]+(a[j]-a[k])*(a[j]-a[k]);                    K[i][j]=k;                }            }        }    }    return dp[m][n];}int main(){    int T,cas=0;    scanf("%d",&T);    while(T--)    {        read();        printf("Case %d: %d\n",++cas,solve());    }    return 0;}