HDU 4532 湫秋系列故事——安排座位 （组合+DP）

湫秋系列故事——安排座位

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 454    Accepted Submission(s): 137

Problem Description

　　为了给腾讯公司找到更多优秀的人才，HR湫秋最近去某高校组织了一次针对该校所有系的聚会，邀请了每个系的一些优秀学生来参加。

　　作为组织者，湫秋要安排他们的座位。这并不是一件很简单的事情，因为只有一排位置，并且位置总数恰好等于参加聚会的人数。为了促进交流，两个来自相同系的同学不可以座位相邻。湫秋现在希望知道有多少种不同的合理安排座位的方法（任意两个合理的安排方法，只要有一个位置的同学不同，都被认为是不同的）。

 

Input

输入第一行为T，表示有T组测试数据。
每组数据一个N开始，表示一共有多少个系。下面的一行包含N个整数Ai，表示每个系的到场人数。

[Technical Specification]
1. 1 <= T <= 47
2. 1 <= N, Ai <= 47
3. 1 <= Sum(Ai) <= 447

 

Output

对每组数据，先输出为第几组数据，然后输出结果。由于结果可能很大，输出对1,000,000,007 取余后的结果。

 

Sample Input

3
2
1 2
2
1 3
3
1 2 3

 

Sample Output

Case 1: 2
Case 2: 0
Case 3: 120

 

Source

2013腾讯编程马拉松复赛第一场（3月29日）

 

Recommend

liuyiding

 

这里有详解：http://www.douban.com/note/269136472/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod=;

long long dp[][];   //表示前i个系中，有j个空位使得该空位旁边为同一个系的位置数

long long C[][];      //先求出组合数，然后再求出排列数

long long A[];       //A[i]表示i个元素的全排列

int a[];

void Init(){

    C[][]=;

    for(int i=;i<;i++){     //求出组合数

        C[i][]=;

        for(int j=;j<i;j++)

            C[i][j]=(C[i-][j-]+C[i-][j])%mod;

        C[i][i]=;

    }

    A[]=A[]=;

    for(int i=;i<;i++)

        A[i]=(A[i-]*i)%mod;

}

int main(){

    //freopen("input.txt","r",stdin);

    Init();

    int t,n,cases=;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]);

        memset(dp,,sizeof(dp));

        dp[][a[]-]=;    //这样的组合数有一个

        long long sum=a[];

        for(int i=;i<=n;i++){

            for(int j=;j<sum;j++)  //对每一种空位

                for(int k=;k<=a[i];k++)    //将a[i]个元素分成k组

                    for(int u=;u<=j && u<=k;u++)   //将u组放到前j个空位中

                        dp[i][j-u+a[i]--(k-)]=(dp[i][j-u+a[i]-k]+(((dp[i-][j]*C[j][u])%mod*C[sum+-j][k-u])%mod*C[a[i]-][k-])%mod)%mod;

            sum+=a[i];

        }

        printf("Case %d: ",++cases);

        long long ans=dp[n][];

        for(int i=;i<=n;i++)   //对每一组，进行全排列

            ans=(ans*A[a[i]])%mod;

        cout<<ans<<endl;

    }

    return ;

}