[BZOJ 1037] 生日聚会Party

Link:

Solution:

由于对任意一段都有要求，于是我们对于所有前缀考虑其后缀不超过$k $即可：

设$dp[i][j][x][y]$为前$i$个人中有$j$个男孩，且后缀中男女最大相差$x$，女男最大相差$y$时的方案数

每次向添加女孩/添加男孩转移。

注意：如果差值为负数时置为$0$，因为无论差了多少，在下一次添加相同性别时最大相差都会变为$1$

Code:

#include <bits/stdc++.h>

using namespace std;

const int MOD=;

const int MAXN=;

int dp[*MAXN][MAXN][][],n,m,k,res=;

int main()

{

    scanf("%d%d%d",&n,&m,&k);dp[][][][]=; //初始值

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

    for(int x=;x<=k;x++) for(int y=;y<=k;y++)

    if(dp[i][j][x][y])

    {

        if(j+<=n && x+<=k) (dp[i+][j+][x+][max(,y-)]+=dp[i][j][x][y])%=MOD;

        if(y+<=k && i+-j<=m) (dp[i+][j][max(,x-)][y+]+=dp[i][j][x][y])%=MOD;

    }

    for(int i=;i<=n;i++) for(int j=;j<=k;j++) for(int x=;x<=k;x++)

        (res+=dp[n+m][i][j][x])%=MOD;

    printf("%d",res);

    return ;

}

Review:

（1）如果转移为向后添加数时，一般用已知数向后转移未知数更方便，而非未知数反推已知数

（2）如果对“任意一段”有要求时，转移时保证每一个前缀的最差后缀都合法即可

巴特西

[BZOJ 1037] 生日聚会Party

Link:

Solution:

Code:

Review:

最新文章

热门文章