首页 > 代码库 > H - 扑克牌 hihocoder1159
H - 扑克牌 hihocoder1159
H - 扑克牌
Problem Description
一副不含王的扑克牌由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等。
Input
第一行为一个整数T，为数据组数。
之后每组数据占一行。这一行首先包含一个整数N，表示给定的牌的张数，接下来N个由空格分隔的字符串，每个字符串长度为2，表示一张牌。每组数据中的扑克牌各不相同。
1 ≤ T ≤ 2000
1 ≤ N ≤ 52
Output
Sample Input
51 TC2 TC TS5 2C AD AC JC JH4 AC KC QC JC6 AC AD AS JC JD KD
Sample Output
Case #1: 1Case #2: 0Case #3: 48Case #4: 24Case #5: 120
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int N=110; 5 const int INF=0x3f3f3f3f; 6 const int mod=1e9+7; 7 int cas=1,T; 8 LL dp[14][55],C[N][N],fac[N]; 9 int a[N],n;10 void init()11 {12 for(int i=0;i<N;i++)13 {14 C[i][0]=C[i][i]=1;15 for(int j=1;j<i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];16 }17 fac[0]=1;18 for(int i=1;i<N;i++) fac[i]=fac[i-1]*i;19 }20 LL Cnm(int n,int m)21 {22 if(m>n || n<0 || m<0) return 0;23 return C[n][m];24 }25 char s[N][3];26 int cmp(const int &a,const int &b)27 {28 return a>b;29 }30 int main()31 {32 //freopen("1.in","w",stdout);33 //freopen("1.in","r",stdin);34 //freopen("1.out","w",stdout);35 init();36 scanf("%d",&T);37 while(T--)38 {39 scanf("%d",&n);40 for(int i=1;i<=n;i++) scanf("%s",s[i]); 41 memset(a,0,sizeof(a));42 for(int i=1;i<=n;i++)43 {44 switch(s[i][0])45 {46 case ‘T‘:a[10]++;break;47 case ‘J‘:a[11]++;break;48 case ‘Q‘:a[12]++;break;49 case ‘K‘:a[13]++;break;50 case ‘A‘:a[1]++;break;51 default:a[s[i][0]-‘0‘]++;break;52 }53 }54 sort(a,a+14,cmp);55 // for(int i=0;a[i];i++) printf("%d %d\n",i,a[i]);56 memset(dp,0,sizeof(dp));57 dp[0][a[0]-1]=1;58 int sum=a[0];59 LL ans=dp[0][0];60 //dp第二维记录有多少个同花色相邻的61 for(int i=1;a[i];i++)62 {63 for(int j=0;j<sum;j++)//多少个相邻64 {65 for(int k=1;k<=a[i];k++)//a[i]分成多少部分66 {67 for(int l=0;l<=k;l++)//多少部分放到相邻的中间68 {69 LL x=j+a[i]-k-l;70 if(x<0) continue;71 dp[i][x]+=Cnm(j,l) * Cnm(sum+1-j,k-l)* Cnm(a[i]-1,k-1) * dp[i-1][j] ;72 }73 }74 }75 sum+=a[i];76 ans=dp[i][0];77 }78 for(int i=0;a[i];i++) ans=ans*fac[a[i]];79 printf("Case #%d: %llu\n",cas++,ans);80 }81 //printf("time=%.3lf\n",(double)clock()/CLOCKS_PER_SEC);82 return 0;83 }
题解：
本题数据加强版：http://acm.hdu.edu.cn/showproblem.php?pid=4532.
这题是一道组合数学dp.
dp数组有两维，对于dp[i][j],i表示放到第几种花色，j记录有多少个同花色相邻的出现,dp[i][j]表示方案数.
dp时，对于a[i]个同一种花色，可以将其划分为k组（将相同的a[i]个球放到k个盒子,盒子不能为空),有C(a[i]-1,k-1)种分法.
然后将k组花色按原来的顺序塞到前面已经排好的方案中,这里又有两种情况：
1.放到普通的位置
2.放到原来同花色相邻的中间，这样j就减小了
假设放l组到相邻花色中间
这里的方案数是从j个同花色相邻的位置中选l个位置出来，则有C(j,l)种方案。
假设前面有sum张牌，则有sum+1个位置，除去j个相邻位置，将剩下的k-l组放进来，有C(sum+1-j,k-l)种放法
所以最终的状态转移为
设x为放完后的同花色相邻，则x=j+a[i]-k-l;
dp[i][x]+=Cnm(j,l) * Cnm(sum+1-j,k-l)* Cnm(a[i]-1,k-1) * dp[i-1][j]
H - 扑克牌 hihocoder1159