「ZJOI2008」生日聚会 - DP

对于任意连续的一段，男孩与女孩的数目之差不超过。假设参加 party 的人中共有个男孩与个女孩，求方案总数。

链接

题解

设表示前个人中，有个男孩，包含第个人的连续区间中，男孩最多比女孩多个，女孩最多比男孩多个，的方案数。

如果第个是男孩

答案即为。

代码

#include <cstdio>
#include <algorithm>

const int MAXN = 150;
const int MAXK = 20;
const int MOD = 12345678;

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);

    // f[i][j][p][q], left i, j boys, max(boys - girls) = p, max(girls - boys) = q
    static int f[MAXN * 2 + 1][MAXN + 1][MAXK + 2][MAXK + 2];
    f[0][0][0][0] = 1;
    for (int i = 0; i < n + m; i++) {
        for (int j = 0; j <= n; j++) {
            for (int p = 0; p <= k; p++) {
                for (int q = 0; q <= k; q++) {
                    // Add a boy
                    (f[i + 1][j + 1][p + 1][std::max(q - 1, 0)] += f[i][j][p][q]) %= MOD;
                    // Add a girl
                    (f[i + 1][j][std::max(p - 1, 0)][q + 1] += f[i][j][p][q]) %= MOD;
                }
            }
        }
    }

    int ans = 0;
    for (int p = 0; p <= k; p++) for (int q = 0; q <= k; q++) (ans += f[n + m][n][p][q]) %= MOD;
    printf("%d\n", ans);

    return 0;
}