HDU1291-Closing Ceremony of Sunny Cup

Tyne ·

更新时间:2024-11-14

· 947 次阅读

The 3rd Zhejiang Provincial Collegiate Programming Contest will be held at Zhejiang University in 05/13/2006. The contest attracts many excellent programmer, of course, including 18 acmers of HDU,They are Lu xiaojun, Wang rongtao,Zhou feng;Gao bo, Li weigang, Xu haidong;Lin le,Lin jie,Li huansen;Mou changqing, Zhou lin, Wang dongdong;Ying qili,Lai li,Weng jianfei;Wang jun,Wang jianxing and Liu qi.

I don’t know which team will be champion,but I know that closure will be held at Linshui Hall,which is a very beautiful classroom near the river.

Now I am thinking a question, supposing attendance is a square number (N^2) and the number of the seat is a square number too( N lines ,and N seats each line), If orgazizer is so bored that they arrange sits according to player’s height (Supposing all players’ heights are dirrerent). The arranging rules can be described as following:

A cannot sit at back of B when A is short than B. A cannot sit at right of B when A is short than B.

The question left to you is that: " How many dirrerent arranging styles you can get according to the rules?"
Input
Input file contains multiple test cases, and each test case is described with an integer N(1<=N<=20),you can get its meaning throught problem description.
Output
For each test case ,you should output a result,and one result per line.
Sample Input
2
3
Sample Output
2
42

分析：

题意：
n阶方阵，在里面在里面填入1~n*n的数字，在填满方阵的同时满足每个位置的左边的数和下边的数都比它小，问满足要求的排列方法有多少种？

感想：
我太难了！想了一晚上都没有想到解法，网上也没有题解，唉！皇天不负有人，终于在vjudge看到了不知道哪个神仙的java代码.于是我从他的代码中总结出了一个公式，我也不知道这公式咋来的，只能问问学长了（公式太长，将分子分母分开）：
公式分子：(n2)!/((n-1)2+1)!
公式分母：(2(n-1)!)2!(2n-1)/(n!)2

代码：

#include
#include
#define N 25
using namespace std;
int dp[N][1005];
int main()
{
	int n;
	dp[1][0]=dp[1][1]=dp[2][0]=1;
	dp[2][1]=dp[3][0]=dp[3][1]=2;
	dp[3][2]=4;
	for(int i=4;i<=20;i++)
	{
		int len=dp[i-1][0],v=0;
		for(int j=0;j<=len;j++)
		{
			dp[i][j]=dp[i-1][j];
		}
		for(int k=(i-1)*(i-1)+1;k<=i*i;k++)
		{
			v=0;
			len=dp[i][0];
			for(int j=1;j<=len;j++)
			{
				dp[i][j]=dp[i][j]*k+v;
				v=dp[i][j]/10;
				dp[i][j]%=10;
			}
			while(v)
			{
				dp[i][++len]=v%10;
				v/=10;
			}
			dp[i][0]=len;
		}
		for(int k=i;k0;j--)
			{
				v=v*10+dp[i][j];
				dp[i][j]=v/(k*k);
				v%=(k*k);
			}
			len=dp[i][0];
			while(!dp[i][len])
			{
				len--;
			}
			dp[i][0]=len;
		}
		v=0;
		for(int j=dp[i][0];j>0;j--)
		{
			v=v*10+dp[i][j];
			dp[i][j]=v/(2*i-1);
			v%=(2*i-1);
		}
		len=dp[i][0];
		while(!dp[i][len])
		{
			len--;
		}
		dp[i][0]=len;
	}
	while(~scanf("%d",&n))
	{
		for(int i=dp[n][0];i>0;i--)
		{
			printf("%d",dp[n][i]);
		}
		printf("\n");
	}
	return 0;
}

作者：IT-LittleM

hdu

1024 个赞