现有 n n 个男生 m m 个女生要坐成一排，需要满足对于任意连续的一段，不存在男女数量之差大于 k k 的情况，其中 n,m,k n, m, k 由输入数据给定。

题解

蛮好的一道DP。可惜我上午做的时候智商不在线。 当时没有仔细考虑「任意连续的区间」，这个限制，导致设出了一个奇怪的状态。

一个自然而然的思路就是从左往右确定方案数，如果我们纪录目前已经有 i i 个男生，j j 个女生的方案数，那么转移的话就是看下一个位置坐男生还是坐女生。

但是这个状态不保证满足题目中的限制，而且由于转移分选男生与选女生，所以应分别记录已经确定的区间当中，男生数目减去女生数目的最大值，以及女生数目减去男生数目的最大值。又由于DP的顺序，只需要记录后缀最大值即可。

公式爆炸，具体看代码就好。

代码

#include <cctype>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
typedef long long ll;
const int MAXN = 160;
const int MAXK = 30;
const int MOD = 12345678;
int n, m, k;
int f[MAXN][MAXN][MAXK][MAXK];
int main() {
    scanf("%d %d %d", &n, &m, &k);
    f[0][0][0][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int a = 0; a <= std::min(i, k); a++) {
                for (int b = 0; b <= std::min(j, k); b++) {
                    if (i < n && a < k) {
                        f[i + 1][j][a + 1][std::max(b - 1, 0)] += f[i][j][a][b];
                        f[i + 1][j][a + 1][std::max(b - 1, 0)] %= MOD;
                    }
                    if (j < m && b < k) {
                        f[i][j + 1][std::max(a - 1, 0)][b + 1] += f[i][j][a][b];
                        f[i][j + 1][std::max(a - 1, 0)][b + 1] %= MOD;
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int a = 0; a <= k; a++) {
        for (int b = 0; b <= k; b++) {
            ans += f[n][m][a][b];
            ans %= MOD;
        }
    }
    printf("%d", ans);
    return 0;
}