首页 > ACM题库 > HDU-杭电 > HDU 4532-湫秋系列故事――安排座位-动态规划-[解题报告]HOJ
2015
07-17

HDU 4532-湫秋系列故事――安排座位-动态规划-[解题报告]HOJ

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

问题描述 :

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

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

输入:

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

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

输出:

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

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

样例输入:

3
2
1 2
2
1 3
3
1 2 3

样例输出:

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

题目:安排座位

 

解析:http://www.douban.com/note/269136472/

 

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

const LL MOD=1000000007;

LL a[550];
LL A[550];
LL C[550][550];
LL dp[55][550];

void Init()
{
    for(int i=0; i<550; i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1; j<i; j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    A[0]=1;
    for(int i=1; i<550; i++)
        A[i]=(A[i-1]*i)%MOD;
}

int main()
{
    Init();
    int T,n,tt=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        memset(dp,0,sizeof(dp));
        dp[1][a[1]-1]=1;
        LL sum=a[1];
        for(int i=2; i<=n; i++)
        {
            for(int j=0; j<sum; j++)        //对每一种空位
                for(int k=1; k<=a[i]; k++)  //将a[i]个元素分成k组
                    for(int u=0; u<=j && u<=k; u++) //将u组放到前j个空位中
                        dp[i][j-u+a[i]-1-(k-1)]=(dp[i][j-u+a[i]-k]+(((dp[i-1][j]*C[j][u])%MOD*C[sum+1-j][k-u])%MOD*C[a[i]-1][k-1])%MOD)%MOD;
            sum+=a[i];
        }
        printf("Case %d: ",tt++);
        LL ans=dp[n][0];
        for(int i=1; i<=n; i++)    //对每一组,进行全排列
            ans=(ans*A[a[i]])%MOD;
        cout<<ans<<endl;
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/10302471