[Codeforces 626F]Group Projects

由於順序不重要，我們乾脆先把這些學生排序好

可以發現，對於每一組，我們只需要關心最大值和最小值

因此，我們可以構造一個$DP$，$DP[g][i]$代表目前有效$imbalance$是$i$，有$g$組還沒完成 (還沒有上界)
當一個學生$s$加進來時，有以下四種情況 (假設從$DP[g][i]$轉移)
轉移後的有效$imbalance$一定是$g*(s-s_{上一個})$，令它為$i_{0}$
1. 加進$g$組中的其中一組，以權重$g$轉移到$DP[g][i_{0}]$
2. 自成新的一組，在新的一組中以$s$當作下界，轉移到$DP[g+1][i_{0}]$
3. 從$g$組中選一組，以$s$當作上界，這組就完成了，以權重$g$轉移到$DP[g-1][i_{0}]$
4. 自成新的一組，且這組只有$s$一個人，轉移到$DP[g][i_{0}]$

可以使用$N*N*K$的三維陣列一層一層轉移，或較省空間的滾動陣列
最終答案即是$\sum_{i=0}^{K} DP[0][i]$

時間複雜度：$O(N^{2}K)$

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL MOD=1000000007LL;
int N,K,S[201];
LL DP[2][201][1001];
void Add(LL &a,const LL &b){(a+=b)%=MOD;}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&K)==2)
    {
        for(int i=1;i<=N;i++)scanf("%d",&S[i]);
        sort(S+1,S+N+1),S[0]=0;
        for(int d=0;d<2;d++)for(int i=0;i<=N;i++)for(int j=0;j<=K;j++)DP[d][i][j]=0LL;
        DP[0][0][0]=1LL;
        int d=0;
        for(int idx=1;idx<=N;idx++,d^=1)
        {
            for(int g=0;g<=N;g++)for(int i=0;i<=K;i++)DP[d^1][g][i]=0LL;
            for(int g=0;g<=N;g++)for(int i=0;i<=K;i++)if(DP[d][g][i])
            {
                const int nxti=i+g*(S[idx]-S[idx-1]);
                if(nxti>K)break;
                Add(DP[d^1][g][nxti],g*DP[d][g][i]);//Add to existing group
                Add(DP[d^1][g+1][nxti],DP[d][g][i]);//Create new group
                if(g>0)Add(DP[d^1][g-1][nxti],g*DP[d][g][i]);//Add to and close one group
                Add(DP[d^1][g][nxti],DP[d][g][i]);//Create and close new group
            }
        }
        LL ans=0LL;
        for(int i=0;i<=K;i++)Add(ans,DP[d][0][i]);
        printf("%I64d\n",ans);
    }
    return 0;
}