洛谷P2592 [ZJOI2008]生日聚会题解

题目链接：P2592 [ZJOI2008]生日聚会

题意：

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

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

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

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

输入格式：

一行共 \(3\) 个整数，分别为男孩数目 \(n\) ，女孩数目 \(m\) ，常数 \(D\) 。

输出格式：

一行答案。

数据范围：

对于 \(100\%\) 的数据， \(n , m \le 150,~D \le 20\)。

~~一开始我还以为是组合数，结果看看好像不太对（~~

显然是区间dp，但是状态如何设计？

这道题最难的就在于：「任意子段男女之差不超过 \(D\) 」导致了朴素的区间dp即使记录了区间 \([i,j]\) 差值不超过 \(k\) ，也无法合并。

于是我们从合并的角度观察加入一个人对整个当前区间的影响

方便起见，我们考虑在区间后面加入了一个人，

不难发现，这会影响到原区间的所有后缀。

于是考虑记录所有后缀的男女个数之差，显然只有极值会产生影响。

设 \(f_{i,j,k,l}\) 表示放了 \(i\) 个男生， \(j\) 个女生，且当前拼出来的区间的所有后缀（包括空串 \(\varnothing\) ），男生个数-女生个数的最大值为 \(k\) ，女生个数-男生个数的最大值为 \(l\) 的方案数。~~（好长啊，要不是看题解我怎么想得出...~~

下面用 \(a\uparrow b\) 表示 a+=b 。

考虑在 \((i,j,k,l)\) 状态的后面加入一个男生，则 \[ f_{i+1,j,k+1,\max\{0,l-1\}} \uparrow f_{i,j,k,l} \] 加入一个女生，则 \[ f_{i,j+1,\max\{0,k-1\},l+1} \uparrow f_{i,j,k,l} \] 注意一下转移的边界，就好了，这个不难，~~主要还是状态设计难~~

最后答案就是 \(\sum\limits_{0 \le k,l \le D} f_{n,m,k,l}\)

时间复杂度 \(O(nmD^2)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(175))
#define K 25
int n,m,D,res=0,f[N][N][K][K];
const int mod = 12345678;

void add(int &x, int y){ (x+=y) >= mod ? x-=mod : 0;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
	cin >> n >> m >> D;
	f[0][0][0][0]=1;
	for(int i=0; i<=n; i++)
		for(int j=0; j<=m; j++)
			for(int k=0; k<=i && k<=D; k++)
				for(int l=0; l<=j && l<=D; l++)
					if(f[i][j][k][l])
					{
						if(i < n && k < D)
							add(f[i+1][j][k+1][max(0ll,l-1)], f[i][j][k][l]);
						if(j < m && l < D)
							add(f[i][j+1][max(0ll,k-1)][l+1], f[i][j][k][l]);
					}
	for(int k=0; k<=D; k++)
		for(int l=0; l<=D; ++l)
			add(res, f[n][m][k][l]);
	cout << res << '\n';
    return 0;
}