$solution:$
如果按照 $A$ 从小到大排序后，极差的计算方式为组内最后加入的数字减去开始插入的数字。
设 $f_{i,j,k}$ 表示前 $i$ 个人，有 $j$ 组还没有最大值，当前和为 $k$ 的方案数，转移考虑 $i$ 选为最大，最小，中间与单独一组即可。答案即为 $\sum_{i=0}^K f_{n,0,i}$。
但是这样 $dp$ 时， $k$ 的取值范围可能很大，超出了 $K$，这样 $dp$ 的时间复杂度为 $O(n^2\sum_{i=1}^n A_i)$ 。
而极差的计算方式可以写成差分，可以将最大值减去最小值变成差分之和，这样的话贡献是递增的，可以只保留 $K$ 以内的 $f$。
直接按照原先的方式转移即可，时间复杂度 $O(n^2k)$ 。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define int long long #define mod 1000000007 using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+c-‘0‘;c=getchar();} return f*ans; } const int N=501; const int K=1001; int f[2][N][K],n,k,A[N],cur; signed main(){ // freopen("4.in","r",stdin); n=read(),k=read() ; for(int i=1;i<=n;i++) A[i]=read();sort(A+1,A+n+1);f[0][0][0]=1; for(int i=1;i<=n;i++){ cur^=1; for(int j=0;j<=i;j++){ for(int p=0;p<=k;p++){ int d=A[i]-A[i-1];f[cur][j][p]=0; if(j&&(p-(j-1)*d)>=0) f[cur][j][p]+=f[cur^1][j-1][p-(j-1)*d],f[cur][j][p]%=mod; if((p-(j+1)*d)>=0&&j+1<=n) f[cur][j][p]+=f[cur^1][j+1][p-(j+1)*d]*(j+1),f[cur][j][p]%=mod; if((p-j*d)>=0) f[cur][j][p]+=f[cur^1][j][p-j*d]*(j+1),f[cur][j][p]%=mod; } } }int res=0; for(int i=0;i<=k;i++) res+=f[cur][0][i],res%=mod; printf("%lld\n",res);return 0; }
原文：https://www.cnblogs.com/si-rui-yang/p/11760963.html
