Steven_Meng's Blog

传送门

比较有意思的$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);
}