【bzoj1037】[ZJOI2008]生日聚会Party

2015.04.27 13:31 Mon | 20次阅读 | 旧日oi | 固定链接 | 源码

Description

今天是hidadz小朋友的生日,她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中,打算坐成一排玩游戏。为了游戏不至于无聊,就座的方案应满足如下条件:对于任意连续的一段,男孩与女孩的数目之差不超过k。很快,小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现,这样的就座方案其实是很多的,所以大家很快就找到了一种,那么到底有多少种呢?热爱数学的hidadz和她的朋友们开始思考这个问题…… 假设参加party的人中共有n个男孩与m个女孩,你是否能解答Susie和hidadz的疑问呢?由于这个数目可能很多,他们只想知道这个数目除以12345678的余数。

Input

仅包含一行共3个整数,分别为男孩数目n, 女孩数目m, 常数k。

Output

应包含一行,为题中要求的答案。

Sample Input

1 2 1

Sample Output

1

HINT

对于100%的数据, n , m ≤ 150,k ≤ 20。

题解

挺普通的dp
dp[i][j][p][q]表示前i个人,j个男的,起点为1~i,终点为i的子序列中最多包含p男生最多的,最多包含q个女生的方案数
转移很好写

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 12345678
#define inf 0x3f3f3f3f
using namespace std;
int dp[301][151][21][21];
int n,m,mx,ans;
int main()
{
    cin>>n>>m>>mx;
    dp[0][0][0][0]=1;
    for(int i=0;i<n+m;i++)
    for(int j=0;j<=n&&j<=i;j++)
    for(int p=0;p<=mx;p++)
    for(int q=0;q<=mx;q++)
    {
        if(j+1<=n&&p<mx) 
        {
            dp[i+1][j+1][p+1][max(0,q-1)]+=dp[i][j][p][q];
            dp[i+1][j+1][p+1][max(0,q-1)]%=mod;
        }
        if(i-j<m&&q<mx) 
        {
            dp[i+1][j][max(p-1,0)][q+1]+=dp[i][j][p][q];
            dp[i+1][j][max(p-1,0)][q+1]%=mod;
        }
    }
    for(int j=0;j<=mx;j++)
    for(int k=0;k<=mx;k++)
    ans=(ans+dp[n+m][n][j][k])%mod;
    cout<<ans<<endl;
}```