cnyz's Blog

• https://www.acwing.com/problem/content/description/339/

考虑 DP。

设 $f_{i,j,k,l,las}$ 表示还剩下 $1$ 张相同花色的牌有 $i$ 张，还剩下 $2$ 张相同花色的牌有 $j$ 张，还剩下 $3$ 张相同花色的牌有 $k$ 张，还剩下 $4$ 张相同花色的牌有 $l$ 张，上一张还剩 $las$ 张。

那么转移就会是从这些类型任意一种中选出一种，然后更新信息即可。

写一个 DFS 即可。

跑满是 $O(14^4\times 4)$ 的，但显然跑不满。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
map<char,int> ch;
int a[20],b[20],n;
int T;
ull f[14][14][14][14][5];
bool vis[14][14][14][14][5];
ull dfs(int x,int y,int a,int b,int las) {
	if(!x&&!y&&!a&&!b) return 1;
	if(vis[x][y][a][b][las]) return f[x][y][a][b][las];
	ull ans=0;
	if(x) ans+=1ull*(x-(las==2))*dfs(x-1,y,a,b,1);
	if(y) ans+=1ull*(y-(las==3))*2*dfs(x+1,y-1,a,b,2);
	if(a) ans+=1ull*(a-(las==4))*3*dfs(x,y+1,a-1,b,3);
	if(b) ans+=1ull*b*4*dfs(x,y,a+1,b-1,4);
	vis[x][y][a][b][las]=1;
	return f[x][y][a][b][las]=ans;
}
int main() {
	for(int i=2;i<=9;i++) ch[i+'0']=i;
	ch['T']=10,ch['J']=11,ch['Q']=12,ch['K']=13,ch['A']=1;
	scanf("%d",&T);
	for(int i=1;i<=T;i++) {
		scanf("%d ",&n);
		char s[5];
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		for(int i=1;i<=n;i++) {
			scanf("%s",s);
			a[ch[s[0]]]++;
		}
		for(int i=1;i<=13;i++) b[a[i]]++;
		printf("Case #%d: %llu\n",i,dfs(b[1],b[2],b[3],b[4],1));
	}
}

小技巧：

• 遇到模数为 $2^{64}$ 的，直接自然溢出啥事没有。
• 遇到状态转移较复杂的 DP 可以考虑记忆化搜索。