计算机学院大学生程序设计竞赛（2015’11）1005 ACM组队安排

1005 ACM组队安排

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

  ACM亚洲区比赛结束，意味着开始备战明年的浙江省大学生程序设计竞赛了！

  杭州电子科技大学ACM集训队也准备开始组队。

  教练想把所有的n个队员组成若干支队伍，原则是每支队伍至少一人，最多三人。

  现在问题来了：如果已知集训队队员的数量n，请你帮教练计算出所有可能的组队方案有多少种。



  特别说明：

  队伍没有编号，即如果有A,B,C三人，{A}{BC}与{BC}{A}是同一种组队情况。

 

Input

输入包含多组测试数据(约1000组)，每组数据占一行，包含一个数字n(0<=n<=20)，表示ACM集训队的队员人数；n为0，表示输入结束。

 

Output

请输出n个队员所有可能的组队方案数，每组输出占一行。

 

Sample Input

1

2

3

4

5

0

 

Sample Output

1

2

5

14

46

 

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<queue>

#include<stack>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<cmath>

#include<string>

#include<algorithm>

#include<iostream>

#define exp 1e-10

using namespace std;

const int N = 25;

const int M = 1005;

const int inf = 1000000007;

const int mod = 2009;

__int64 dp[N][N][N][N],c[N][N];

int main()

{

    int i,j,k,l,n,x,y;

    __int64 sum;

    for(i=0; i<=20; i++)

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

            if(j==0||i==j)

                c[i][j]=1;

            else

                c[i][j]=c[i-1][j]+c[i-1][j-1];

    for(i=1; i<=20; i++)

        for(l=0; l<=20; l++)

            for(k=0; k<=20; k++)

            {

                j=i-3*l-2*k;

                if(j<0||j==0&&k==0&&l==0)

                    continue;

                dp[i][j][k][l]=1;

                y=i;

                for(x=1; x<=k; x++,y-=2)

                    dp[i][j][k][l]*=c[y][2];

                for(x=1; x<=k; x++)

                    dp[i][j][k][l]/=x;

                for(x=1; x<=l; x++,y-=3)

                    dp[i][j][k][l]*=c[y][3];

                for(x=1; x<=l; x++)

                    dp[i][j][k][l]/=x;

            }

    while(scanf("%d",&n)&&n)

    {

        sum=0;

        for(j=0; j<=20; j++)

            for(k=0; k<=20; k++)

                for(l=0; l<=20; l++)

                    if(j+2*k+3*l==n)

                    {

                        sum+=dp[n][j][k][l];

                    }

        printf("%I64d\n",sum);

    }

    return 0;

}

总是望着曾经的空间发呆，那些说好不分开的朋友不在了，转身，陌路。 熟悉的，安静了， 安静的，离开了， 离开的，陌生了， 陌生的，消失了， 消失的，陌路了。