bzoj1037
题意
\(n\)个男孩，\(m\)个女孩，共\(n+m\)个排成一排。
要求对于任意连续的一段，男孩与女孩的数目之差不超过\(k\)。
求排列的方案数。
\(1\leq n,m\leq 150\)
\(1\leq k\leq 20\)
分析
计数问题，我们考虑递推求解。设\(f[i][j]\)表示当前用了\(i\)个男孩，\(j\)个女孩的方案数。
我们的目标是要从\(f[i][j]\)推导\(f[i+1][j]\)和\(f[i][j+1]\)。即指针向右一位位地移动。
每次移动都要满足要求，即以当前终点往左任意长度的区间，男孩和女孩的个数之差不超过\(k\)。
所以只需要满足当前终点往左任意长度的区间中，男孩和女孩的个数之差的最大值不超过\(k\)。
这提示我们再多记录二元：设\(f[i][j][k][l]\)表示当前用了\(i\)个男孩，\(j\)个女孩，以第\(i+j\)个位置往左任意长度的区间中，男孩最多比女孩多\(k\)个，女孩最多比男孩多\(j\)个的方案数。
发现这是可以通过连续性转移的。
