一开始想到用dp[i][j]表示前i个人中有j个男孩的状态，但是发现没法转移，有后效性。所以我们还要多加两维状态，去保证无后效性。为了方便转移，还要是和i结尾有关，即与后缀有关。 dp[i][j][x][y]表示前i个人中有j个男孩，前i个人的后缀中男孩最多比女孩多x人，女孩最多比男孩多y人。有两种转移决策： （1）i+1若是个男孩，可以转移到dp[i+1][j+1][x+1][y?y-1:0]。 （2）i+1若是个女孩，可以转移到dp[i+1][j][x?x-1:0][y+1]。 证：如果前i个人中任何一个后缀中女孩都不比男孩多，则记y=0，如果后面又加了一个男孩，则y还是等于0，如果加了一个女孩，那y=1，即她自己这个后缀中只有她自己一个女孩，为最大。反之同理。
#include <cstdio> #include <cstring> int n,m,k,dp[301][151][21][21]; #define mod 12345678 int main(){ // freopen("a.in","r",stdin); scanf("%d%d%d",&n,&m,&k); dp[0][0][0][0]=1; for(int i=0;i<=n+m;++i) for(int j=0;j<=n;++j) for(int x=0;x<=k;++x) for(int y=0;y<=k;++y) if(dp[i][j][x][y]){ if(j+1<=n&&x+1<=k) dp[i+1][j+1][x+1][y?y-1:0]+=dp[i][j][x][y], dp[i+1][j+1][x+1][y?y-1:0]%=mod; if(i-j+1<=m&&y+1<=k) dp[i+1][j][x?x-1:0][y+1]+=dp[i][j][x][y], dp[i+1][j][x?x-1:0][y+1]%=mod; } int ans=0; for(int i=0;i<=k;++i) for(int j=0;j<=k;++j) ans=(ans+dp[n+m][n][i][j])%mod; printf("%d\n",ans); return 0; }