Description：

一个 $01$ 序列，要求任何一个区间 $0$ 和 $1$ 的个数差不超过 $k$ ，求方案数。

$1\leqslant n\leqslant 150,1\leqslant k\leqslant 20$

Solution：

一个通用的优化思路是考虑一个计算是不是有冗余，对于这个，其实发现我们只要计算每个后缀的个数就行了，因为已经结束的肯定不用考虑，又思考了一下发现只有男生和女生差的最大值是有用的，因为较小的在以后也不会成为最大的，于是设状态为 $f[i][j][k][l]$ 表示 $i$ 个男生 $j$ 个女生，男生比女生最大多 $k$ ，女生比男生最大多 $l$ 的方案数，有了这么好用的状态，转移也就很好写：

最后一个放男生： $f[i+1][j][k+1][\max(l-1,0)]+=f[i][j][k][l]$

最后一个放女生： $f[i][j+1][\max(k-1,0)][l+1]+=f[i][j][k][l]$

之所以和 $0$ 取 $\max$ 是因为最后一个没有任何一个人的后缀是 $0$ ，所以不会比 $0$ 小。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,d;

#define MAXN 200

#define MAXK 30

int f[MAXN][MAXN][MAXK][MAXK];

#define MOD 12345678

int main()

{

	scanf("%d%d%d",&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 <= d;++k)

			{

				for(int l = 0;l <= d;++l)

				{

					f[i + 1][j][k + 1][max(l - 1,0)] = (f[i + 1][j][k + 1][max(l - 1,0)] + f[i][j][k][l]) % MOD;

					f[i][j + 1][max(k - 1,0)][l + 1] = (f[i][j + 1][max(k - 1,0)][l + 1] + f[i][j][k][l]) % MOD;

				}

			}

		}

	}

	int ans = 0;

	for(int i = 0;i <= d;++i)

	{

		for(int j = 0;j <= d;++j)

		{

			ans = (ans + f[n][m][i][j]) % MOD;

		}

	}

	cout << ans << endl;

	return 0;

}