球和盒子的组合问题 动态规划式.txt

ACM资料大集合

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

//球和盒子的组合问题 Push Button Lock
//浙大ACM 2775

#define MAX 13
long c[MAX][MAX];


long jiechen(long num)
{
	if(num==0) return 1;
	else return num*jiechen(num-1);
} 

void cal()
{
	long i,j;
	for(i=1;i<=MAX;i++)
	{
		c[i][1]=1;
		c[i][i]=jiechen(i);
	}
	for(i=2;i<=MAX;i++)
	{
		for(j=2;j<i;j++)
			c[i][j]=c[i-1][j-1]*j+c[i-1][j]*j;//动态规划函数
	}
}

long ccc(long a,long b)
{
	return jiechen(a)/(jiechen(b)*jiechen(a-b));
}

void print()
{
	long i,j;
	for(i=1;i<7;i++)
	{
		for(j=1;j<7;j++)
			printf("%4d",c[i][j]);
		cout<<endl;
	}
	for(i=1;i<7;i++)
	{
		for(j=1;j<=i;j++)
			printf("%3d",ccc(i,j));
		printf("\n");
	}
}
int main()
{
	long sum;
	int i,j,k;
	int num,count;
	cin>>count;
	cal();
	for(i=0;i<count;i++)
	{
		cin>>num;
		sum=0;
		for(j=1;j<=num;j++)
			for(k=1;k<=j;k++)
			sum+=c[j][k]*ccc(num,j);
		cout<<i+1<<" "<<num<<" "<<sum<<endl;
	}
	return 0;
}