题目描述
一副不含王的扑克牌由52张牌组成,由红桃、黑桃、梅花、方块4组牌组成,每组13张不同的面值。
现在给定52张牌中的若干张,请计算将它们排成一列,相邻的牌面值不同的方案数。
算法1
(暴力dp) $O(nb_i^{a_i})$
直接记一个 $f(x_1,x_2,x_3,x_4,\cdots,x_{13},t)$ 表示 A 有几张牌,2 有几张牌,3 有几张牌,以此类推,一直到 K 有几张牌,再记一个上一张牌放的是什么。
直接枚举这一张牌放啥,即可。
算法2
(优化状态的dp) $O(a_i^{b_i})$
我们发现这个问题在 $a$ 的出现次数上有一个很小的限制,所以我们考虑从这里入手。
然后就会发现有一个很好的事情:如果两个 $a$ 在原序列的出现次数相同,那么这两种 $a$ 是可以交换的。
于是就有一个更快的方法出现了:
设 $f(c_1,c_2,c_3,c_4,t)$ 为目前的序列中,出现了 $1$ 次的 $a$ 有 $c_1$ 个,出现了 $2$ 次的 $a$ 有 $c_2$ 个,出现了 $3$ 次的 $a$ 有 $c_3$ 个,出现了 $4$ 次的 $a$ 有 $c_4$ 个,最后一个数对应的 $a$ 出现了 $t$ 次。
然后,因为相邻数不能相同,所以如果这次的出现次数恰好等于上一个的出现次数减 $1$,那么能够转移的 $a$ 数量就会少一种。依照这个就可以得到转移了。
总复杂度是 $O(13^4\times 4^2)$,可以通过。
具体见代码。
C++ 代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int qread() {
register char c = getchar();
register int x = 0, f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + c - 48;
c = getchar();
}
return x * f;
}
inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}
unsigned long long dp[14][14][14][14][5];
bool vis[14][14][14][14][5];
inline bool Valid(int cnt0, int cnt1, int cnt2, int cnt3, int cnt4, int lst) {
if (cnt0 < 0 || cnt0 > 13) return 0;
if (cnt1 < 0 || cnt1 > 13) return 0;
if (cnt2 < 0 || cnt2 > 13) return 0;
if (cnt3 < 0 || cnt3 > 13) return 0;
if (cnt4 < 0 || cnt4 > 13) return 0;
return 1;
}
inline unsigned long long Dfs(int j, int k, int l, int m, int lst) {
//printf("%d %d %d %d %d\n", j, k, l, m, lst);
register unsigned long long &ans = dp[j][k][l][m][lst];
if (vis[j][k][l][m][lst]) return ans;
vis[j][k][l][m][lst] = 1;
ans = 0;
if (j) ans += Dfs(j - 1, k, l, m, 0) * (unsigned long long)((lst != 1) ? j : j - 1);
if (k) ans += Dfs(j + 1, k - 1, l, m, 1) * (unsigned long long)((lst != 2) ? k : k - 1);
if (l) ans += Dfs(j, k + 1, l - 1, m, 2) * (unsigned long long)((lst != 3) ? l : l - 1);
if (m) ans += Dfs(j, k, l + 1, m - 1, 3) * (unsigned long long)m;
//printf("%d %d %d %d %d %llu\n", j, k, l, m, lst, ans);
return ans;
}
inline int readNum() {
register char c = getchar();
while ((c < '2' || c > '9') && c != 'A' && c != 'K' && c != 'Q' && c != 'J' && c != 'T') c = getchar();
if (c >= '2' && c <= '9') return c - '0';
else if (c == 'A') return 1;
else if (c == 'T') return 10;
else if (c == 'J') return 11;
else if (c == 'Q') return 12;
else if (c == 'K') return 13;
}
inline void Solve() {
dp[0][0][0][0][0] = 1;
vis[0][0][0][0][0] = 1;
register int t = qread();
for (register int ca = 1;ca <= t;ca++) {
register int n = qread(), cnt[20] = {0}, cntcnt[20] = {0};
for (register int i = 1;i <= n;i++) cnt[readNum()]++;
register unsigned long long ans = 1;
for (register int i = 1;i <= 13;i++) {
cntcnt[cnt[i]]++;
if (cnt[i] == 2) ans *= 2;
else if (cnt[i] == 3) ans *= 6;
else if (cnt[i] == 4) ans *= 24;
}
cout << "Case #" << ca << ": " << ans * Dfs(cntcnt[1], cntcnt[2], cntcnt[3], cntcnt[4], 4) << endl;
}
}
int main() {
Solve();
#ifndef ONLINE_JUDGE
while (1);
#endif
return 0;
}
stO ClCN Orz
stO ClCN Orz
stO ClCN Orz