CF626F 题解
简要题意：
有\(n\)个学生，每个学生有一个能力值\(a_i\)。现在要把这些学生分成一些(任意数量的)组，每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过\(k\)的分组方案总数。
首先，无论我们怎么选，每个组的不和谐度只与他们组内的能力值最大者和能力值最小者有关
所以我们可以将\(a_i\)从小到大排序
考虑DP：
\(f_{i,j,k}\)表示我们枚举到第\(i\)个人，有\(j\)组是已经有能力最小者，但没有能力最大者的组，当前的不和谐度为\(k\)
因为我们有\(j\)组没有能力最大者的人，所以对于\(a_i\)与\(a_{i-1}\)的差，会被计算\(j\)次
令\(p=(a_i-a_{i-1})*j\)
考虑转移：
\(1\)、第\(i\)个数单独一个数为一组，该组能力最大者为它：\(f_{i,j,k+p}=f_{i,j,k}\)
\(2\)、第\(i\)个数为前面\(j\)组中某个组的中间值：\(f_{i,j,k+p}=f_{i,j,k}*j\)
\(3\)、第\(i\)个数为前面\(j\)组中某个组的能力最大者：\(f_{i,j-1,k+p}=f_{i,j,k}*j\)
\(4\)、第\(i\)个数新开一组，但该组未有能力最大者：\(f_{i,j+1,k+p}=f_{i,j,k}\)
优化：
对于\(f_i\)只与\(f_{i-1}\)中的数有关，所以我们可以降维，将\(i\)这一维变成\(0/1\)。
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=201,M=1001,mod=1e9+7;
ll n,k,a[N],p,ans,op;
ll f[2][N][M],f1[2][N][M];
int main()
{
scanf("%lld %lld",&n,&k);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);
f[0][0][0]=1;
for(ll i=1;i<=n;i++)
{
op^=1;
for(ll j=0;j<=n;j++)
for(ll q=0;q<=k;q++)
f[op][j][q]=0;
for(ll j=0;j<=n;j++)
{
p=(a[i]-a[i-1])*j;
for(ll q=0;q<=k-p;q++)
{
f[op][j][q+p]=(f[op][j][q+p]+(f[op^1][j][q]*(j+1))%mod)%mod;
if(j!=0) f[op][j-1][q+p]=(f[op][j-1][q+p]+(f[op^1][j][q]*j)%mod)%mod;
if(j!=n) f[op][j+1][q+p]=(f[op][j+1][q+p]+f[op^1][j][q])%mod;
}
}
}
for(ll i=0;i<=k;i++)
ans=(ans+f[op][0][i])%mod;
printf("%lld\n",ans);
return 0;
}