题解 | #Briefcases Full of Money#

题目描述：

小Q刷题计划在m天刷n题，每题有个难度值，定义难度为每天刷的题最大难度值与最小难度值差的平方，整个计划的

难度为每一天难度的总和。小Q可以按照任意顺序刷题，一天可以刷多道，每题只做一次，求总难度最小值。

分析与思路：

首先将所有的题目从大到小排序，以方便我们在后面算出难度值差。

由题目定义每一天难度值为d[i]
枚举每一天以及当这一天做到第k道题时的最小 。要得到最小就要枚举每天做的题的最小难度值。

由此可得状态转移方程为dp[i][k]=min(dp[i][k],dp[i-1][j-1]+(a[k]-a[j])*(a[k]-a[j]));

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=600;
ll a[N],dp[N][N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i];
        memset(dp,0x3f3f3f3f,sizeof(dp));
        dp[0][0]=0;
        sort(a+1,a+1+n);
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                for(int k=j;k<=n;k++)
                    dp[i][k]=min(dp[i][k],dp[i-1][j-1]+(a[k]-a[j])*(a[k]-a[j]));
        printf("%lld\n",dp[m][n]);
    }
    return 0;
}