洛谷2592 [ZJOI2008]生日聚会

Luogu

BZOJ

分析

设$f[i][j][k][l]$表示前$i$个位置,有$j$个男孩,男孩和女孩数目之差最大为$k$,最小为$l$的方案数。

边界为$f[0][0][0][0]=1$,答案为$\sum\limits_{i=0}^{k}\sum\limits_{j=0}^kf[n+m][n][i][j]$。

转移应该比较简单?看代码应该都能懂吧qwq

时间复杂度$O(n^2k^2)$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=150+5;
const int K=20+5;
const int MOD=12345678;

int n,m,k;
int f[N<<1][N][K][K];

inline void add(int& x,int y) { x+=y; if (x>=MOD) x-=MOD; }

int main() {
    n=read(),m=read(),k=read();
    f[0][0][0][0]=1;
    for (re int i=1;i<=n+m;++i)
        for (re int j=0;j<=min(i,n);++j)
            for (re int p=0;p<=k;++p)
                for (re int q=0;q<=k;++q) {
                    if (!f[i-1][j][p][q]) continue;
                    if (j<n&&p!=k)
                        add(f[i][j+1][p+1][max(0,q-1)],f[i-1][j][p][q]);
                    if (i-j-1<m&&q!=k)
                        add(f[i][j][max(0,p-1)][q+1],f[i-1][j][p][q]);
                }
    int ans=0;
    for (re int p=0;p<=k;++p)
        for (re int q=0;q<=k;++q)
            add(ans,f[n+m][n][p][q]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 02 PM

发表评论