【CodeForces】626 F. Group Projects 动态规划

【题目】F. Group Projects

【题意】给定k和n个数字ai，要求分成若干集合使得每个集合内部极差的总和不超过k的方案数。n<=200，m<=1000，1<=ai<=500。

【算法】动态规划

【题解】每个集合的最小值和最大值非常重要，将序列从小到大排序后，每个集合可以视为最小值到最大值的一条线段。

设$f[i][j][k]$表示前i个数，当前有j条线段没有结束，总和为k的方案数。

转移的关键在于集合权值的拆分，转化为算每个数的贡献。数字a[i+1]的贡献就是覆盖的线段条数，即$t=(a[i+1]-a[i])*j$，分类讨论：

是一条线段的起点和终点

$$f[i+1][j][k+t]+=f[i][j][k]$$

即不是起点，又不是终点

$$f[i+1][j][k+t]+=f[i][j][k]*j$$

是起点，不是终点

$$f[i+1][j+1][k+t]+=f[i][j][k]$$

是终点，不是起点

$$f[i+1][j-1][k+t]+=f[i][j][k]*j$$

复杂度O(n^2*m)。

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=,K=,MOD=1e9+;

int n,m,a[N],f[N][N][K];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    sort(a+,a+n+);

    f[][][]=f[][][]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            int t=(a[i+]-a[i])*j;

            for(int k=;k+t<=m;k++){

                int x=f[i][j][k];

                f[i+][j][k+t]=(f[i+][j][k+t]+1ll*x*(j+))%MOD;

                f[i+][j+][k+t]=(f[i+][j+][k+t]+x)%MOD;

                if(j)f[i+][j-][k+t]=(f[i+][j-][k+t]+1ll*x*j)%MOD;

            }

        }

    int ans=;

    for(int i=;i<=m;i++)ans=(ans+f[n][][i])%MOD;

    printf("%d",ans);

    return ;

}