原题链接：Group Projects
题意
有
\(n\) 个学生，每个学生有一个能力值 \(a_{i}\) 。现在要把这些学生分成一些(任意数量的)组，每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过 \(k\) 的分组方案总数。
思路
根据题目，和数据范围：\(1<=n<=200 , 0<=k<=1000\)，很容易想到三维\(dp\)。我们不妨尝试设\(dp_{i,j,k}\)表示选到第\(i\)个数，分成了\(j\)个组，不和谐度为\(k\)时的方案数。但细想后会发现这样很难转移，因为每个数对每个组的不和谐度的贡献很难计算。因此我们需要用到一个优化技巧——动态维护不和谐度。
因为不和谐度是最大值减最小值，所以首先可以对数组进行排序。然后我们可以举个例子。假设有一个序列（排序后）：\(2, 3, 5, 7, 8\)。
假设只把它分成一个组，则分到\(7\)时不和谐度为\(7 - 2 = 5\)，然后选择到\(8\)时的不和谐度为\(8 - 2 = 6\)。所以\(8\)这个数的贡献其实就是\(8 - 7\)。即第\(i\)个数的贡献为\(a_{i} - a_{i - 1}\)。
设\(dp_{i,j,k}\)表示选到第\(i\)个数时前面有\(j\)个组没有终点，不和谐度为\(k\)时的方案数。
因为第\(i\)个数时前面有\(j\)个组没有终点，所以第\(i\)个数的贡献为\((a_{i + 1} - a_{i}) * j\)，设\(t = (a_{i + 1} - a_{i}) * j\)。
于是可以得出方程：
-
\(dp[i + 1][j][k + t] = dp[i + 1][j][k + t] + dp[i][j][k]\);
-
当前点自己为一组
-
\(dp[i + 1][j][k + t] = dp[i][j][k] * j + dp[i + 1][j][k + t]\);
-
当前点为一个组中间的点
-
\(dp[i + 1][j + 1][k + t] = dp[i + 1][j + 1][k + t] + dp[i][j][k]\);
-
当前点为一个组的起点
-
\(dp[i + 1][j - 1][k + t] = dp[i][j][k] * j + dp[i + 1][j - 1][k + t]\);
-
当前点为一个组的终点
Code
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
const int MAXN = 2e2 + 10,MAXM = 1e3 + 10;
const int mod = 1e9 + 7;
int n,a[MAXN],dp[MAXN][MAXN][MAXM],K,ans;
bool cmp(int x,int y){return x < y;}
signed main()
{
cin >> n >> K;
for(int i = 1;i <= n;i++) cin >> a[i];
sort(a + 1,a + n + 1,cmp);
dp[0][0][0] = 1;
for(int i = 0;i < n;i++)
{
for(int j = 0;j <= n;j++)
{
int t = (a[i + 1] - a[i]) * j;
for(int k = 0;k <= K - t;k++)
{
dp[i + 1][j][k + t] = (dp[i + 1][j][k + t] + dp[i][j][k]) % mod;
dp[i + 1][j][k + t] = (int)((ll)dp[i][j][k] * (ll)j % mod + (ll)dp[i + 1][j][k + t]) % mod;
if(j != n) dp[i + 1][j + 1][k + t] = (dp[i + 1][j + 1][k + t] + dp[i][j][k]) % mod;
if(j != 0) dp[i + 1][j - 1][k + t] = (int)((ll)dp[i][j][k] * (ll)j % mod + (ll)dp[i + 1][j - 1][k + t]) % mod;
}
}
}
for(int i = 0;i <= K;i++) ans = (dp[n][0][i] + ans) % mod;
cout << ans;
return 0;
}