P2592 [ZJOI2008]生日聚会

比较有意思的 $DP$ 题目，考虑转化题目条件：

原题目：对于任意连续的一段，男女数目之差不超过 $k$

转化成：对于所有的连续的段，男女数目之差的最大值不超过 $k$

然后就可以 $DP$ 了，令 $dp[i][j][x][y]$ 为前 $i+j$ 人中 $i$ 人为男孩， $j$ 人为女孩，对于前 $i+j$ 人中所有连续的段，男减女最多 $x$ 人，女减男最多 $y$ 人的方案数。

考虑新加进的是男孩，即 $dp[i+1][j][x+1][max(y-1,0)]+=dp[i][j][x][y]$

新加进的是女孩，即 $dp[i][j][max(x-1,0)][y]+=dp[i][j][x][y]$

时间复杂度 $O(nmk^2)$

#include <bits/stdc++.h>
#define MAXN 155
#define MAXM 25
#define MOD 12345678
using namespace std;
int dp[MAXN][MAXN][MAXM][MAXM];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int main(){
    int n=read(),m=read(),k=read();
    dp[0][0][0][0]=1;
    for (register int i=0;i<=n;++i){
        for (register int j=0;j<=m;++j){
            for (register int x=0;x<=k;++x){
                for (register int y=0;y<=k;++y){
                    dp[i+1][j][x+1][max(y-1,0)]+=dp[i][j][x][y];
                    dp[i+1][j][x+1][max(y-1,0)]%=MOD;
                    dp[i][j+1][max(0,x-1)][y+1]+=dp[i][j][x][y];
                    dp[i][j+1][max(0,x-1)][y+1]%=MOD;
                }
            }
        }
    }
    int ans=0;
    for (register int i=0;i<=k;++i){
        for (register int j=0;j<=k;++j){
            ans=(ans+dp[n][m][i][j])%MOD;
        }
    }
    printf("%d\n",ans);
}