Rockdu's Blog

题目描述

今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中，打算坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件：

对于任意连续的一段，男孩与女孩的数目之差不超过k。

很快，小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的hidadz和她的朋友们开始思考这个问题……

假设参加party的人中共有n个男孩与m个女孩，你是否能解答Susie和hidadz的疑问呢？由于这个数目可能很多，他们只想知道这个数目除以12345678的余数。

输入输出格式

输入格式：

输入文件party.in仅包含一行共3个整数，分别为男孩数目n, 女孩数目m, 常数k。

输出格式：

输出文件party.out应包含一行，为题中要求的答案。

输入输出样例

1 2 1

1

说明

对于30%的数据，n , m ≤ 20；

对于100%的数据, n , m ≤ 150，k ≤ 20。

考虑本题的本质，条件等价于构造一个01序列，使每一个子区间0/1个数的差不超过k，最后把答案乘0个数的阶乘和1个数的阶乘。

那么我们设dp[i][j]表示一共i个人，选了j个男生的状态。每一次我们考虑以i为右端点的所有区间是否合法，容易发现如果对于每一个i作为右端点都合法那么整个序列就是合法的。那么合法的本质条件是什么呢？只要差最大的区间合法那么其他区间也合法。考虑时刻维护差最大的区间的差是多少，观察到如果当前决策放一个男生，那么有两种情况：1、最大区间是男生个数-女生个数造成的，最大区间的差+1。2、最大区间是女生个数-男生个数造成的，最大区间的差-1。反之是相似的，因此我们维护男-女的最大值和女-男的最大值就可以了，如果最大值即将被减成负数，那么最大值为0。因为如果从当前位置往后接，从空区间往后接显然是最优的，因为空区间等价于最大值为0，而前面的差的最大值都已经是负数。

#include<cstdio>
#include<cstring>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 305;
const int maxk = 45;
const int mod = 12345678;
int now;
int dp[2][maxn][maxk][maxk], N, n, m, k;
int boy, girl, mxb_g, mxg_b, ans;
void Add(int & x, const int &a) {
    x += a; if(x >= mod) x -= mod;
}

int main() {
    scanf("%d%d%d", &n, &m, &k), now = 0;
    dp[0][0][0][0] = 1, N = n + m;
    For(i, 0, N - 1) {
        memset(dp[now ^ 1], 0, sizeof(dp[now ^ 1]));
        For(j, 0, i) {
            boy = j, girl = i - j;
            For(d1, 0, k) {
                For(d2, 0, k) {
                    //安排女生 
                    if(d2 < k)
                        if(d1 > 0) Add(dp[now ^ 1][j][d1 - 1][d2 + 1], dp[now][j][d1][d2]);
                        else Add(dp[now ^ 1][j][d1][d2 + 1], dp[now][j][d1][d2]);
                    //安排男生
                    if(d1 < k)
                        if(d2 > 0) Add(dp[now ^ 1][j + 1][d1 + 1][d2 - 1], dp[now][j][d1][d2]);
                        else Add(dp[now ^ 1][j + 1][d1 + 1][d2], dp[now][j][d1][d2]); 
                }
            }
        }
        now ^= 1;
    }
    For(i, 0, k) For(j, 0, k)
        Add(ans, dp[now][n][i][j]);
    printf("%d", ans);
    return 0;
}