hihocoder #1159 : 扑克牌

描述

一副不含王的扑克牌由52张牌组成，由红桃、黑桃、梅花、方块4组牌组成，每组13张不同的面值。现在给定52张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。

牌的表示方法为XY，其中X为面值，为2、3、4、5、6、7、8、9、T、J、Q、K、A中的一个。Y为花色，为S、H、D、C中的一个。如2S、2H、TD等。

解题报告:

用时:2h,3WA

写的二维状态，\(f[i][j]\)表示前i堆牌，有\(j\)个相同牌相邻的位置，那么考虑新加入的牌可以产生的贡献，可以用来新加入相邻位置，也可以用来消除相邻位置，但是有个地方需要注意：对于插入来消除一个相邻位置的牌，可以是一张也可以是多张，所以需要枚举分组，同一组的用来消除或添加同一个位置，这样可以做到不重不漏，所以需要枚举集合，即选出\(l\)个集合，每一个集合至少含有一个元素的方案数 , 为: \(C（a[i]-1,l-1）\)，\(a[i]\)为面值为i的牌的数量，相当于有\(a[i]-1\)个隔板选择\(l-1\)个，最后因为同一种牌内每一张牌不是等价的，所以还要乘上每一种牌的排列即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef unsigned long long ll;

const int N=105;

ll f[N][N],c[N][N];int n,a[N],kase=0;char s[3];

int getid(){

	if(s[0]>='2' && s[0]<='9')return s[0]-'1';

	if(s[0]=='T')return 9;if(s[0]=='J')return 10;

	if(s[0]=='Q')return 11;if(s[0]=='K')return 12;

	return 13;

}

void work()

{

	memset(a,0,sizeof(a));

	scanf("%d",&n);

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

		scanf("%s",s);

		a[getid()]++;

	}

	memset(f,0,sizeof(f));

	f[0][0]=1;

	int tot=0;

	for(int i=1;i<14;i++){

		for(int j=0;j<=tot;j++){

			if(a[i]==0)f[i][j]+=f[i-1][j];

			for(int l=1;l<=a[i];l++)

				for(int k=0;k<=l && k<=j;k++){

					f[i][j-k+a[i]-l]+=

               f[i-1][j]*c[j][k]*c[tot+1-j][l-k]*c[a[i]-1][l-1];

				}

		}

		tot+=a[i];

	}

	ll ans=f[13][0];

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

		for(int j=1;j<=a[i];j++)

			ans*=j;

	printf("Case #%d: %llu\n",++kase,ans);

}

int main()

{

	for(int i=0;i<N;i++){

		c[i][0]=1;

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

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

	}

	int T;cin>>T;

	while(T--)work();

	return 0;

}