https://www.zybuluo.com/ysner/note/1312308
题面
问给(n)个男孩和(m)个女孩排序，使得对于任意连续一段，男女孩数目之差小于等于(k)的方案数。
- (n,mleq150,kleq20)
解析
任意连续一段这个要求好迷啊，不会设状态。。。
那就学习一下。
设男孩为(1)，女孩为(-1)。
然后我们可以把当前序列的后缀最大值和后缀最小值加入状态。
于是就成了，设(f[i][j][k][l])表示到第(i)个人，排了(j)个男孩，后缀最大值为(k)，最小值为(-l)的方案数。
(k)和(l)都不会到负数，具体可参考最大子段和的贪心思想。
复杂度(O(n^2k^2))，空间要卡着开。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int mod=12345678;
int n,m,K,f[22][22][152][302],ans;
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void add(re int &x,re int y){x+=y;if(x>=mod) x-=mod;}
int main()
{
n=gi();m=gi();K=gi();
f[0][0][0][0]=1;
fp(i,1,n+m)
fp(j,0,min(i,n))
fp(k,0,K)
fp(l,0,K)
{
if(!f[k][l][j][i-1]) continue;
if(j<n&&k<K) add(f[k+1][max(0,l-1)][j+1][i],f[k][l][j][i-1]);
if(i-1-j<m&&l<K) add(f[max(0,k-1)][l+1][j][i],f[k][l][j][i-1]);
}
fp(i,0,K) fp(j,0,K) add(ans,f[i][j][n][n+m]);
printf("%d
",ans);
return 0;
}