[ZJOI2008]生日聚会

DP 排列 计数

题面

问给$n$个男孩和$m$个女孩排序，使得对于任意连续一段，男女孩数目之差小于等于$k$的方案数。

• $n,m\leq150,k\leq20$

解析

任意连续一段这个要求好迷啊，不会设状态。。。

那就学习一下。
设男孩为$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\n",ans);
  return 0;
}