「GXOI / GZOI2019」宝牌一大堆

麻将.jpg

观察牌型和计算方法可知，选择一个杠与选择一个面子对于牌型的贡献是等价的

而选择一个杠的答案一定没有选择一个刻子优，因此是没有任何意义的

除去 “七对子” “国士无双” 的特殊情况后，此外的情况就是选择 4个面子 + 1个雀头

容易想到对于每个花色dp得到选择$i$个面子$j$个雀头的答案，然后背包合并

为了$dp$顺子的情况，可以存储前面两个位置作为顺子头的个数

令$dp_{i,j,a,b}$表示当前选了$i$个面子，$j$个雀头，上两个位置选了$a$个顺子，上一个位置选了$b$个顺子

暴力维护dp即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
const int INF=1e9+10;

int min(int x,int y,int z){ return min(min(x,y),z); }

int n,m;
int C[5][5],c[4][12],mk[4][12];
ll ans,val[5][2];

void Check7(){
	static int val[40],cnt;
	cnt=0;
	rep(i,0,3) rep(j,0,9) if(c[i][j]>=2) val[++cnt]=C[c[i][j]][2]<<(mk[i][j]*2);
	if(cnt<7) return;
	sort(val+1,val+cnt+1,greater<int>());
	ll res=7;
	rep(i,1,7) res*=val[i];
	cmax(ans,res);
}

void Check13(){
	ll res=13,x=0,y=0;
	auto chk=[&](ll a,ll b) {
		if(!x) x=a,y=b;
		if(x*b<a*y) x=a,y=b;
	};
	rep(i,0,2) {
		if(!c[i][0] || !c[i][8]) return;
		res*=c[i][0]*c[i][8];
		res<<=(mk[i][0]+mk[i][8]);
		if(c[i][0]>=2) chk(C[c[i][0]][2]<<(mk[i][0]*2),c[i][0]<<mk[i][0]);
		if(c[i][8]>=2) chk(C[c[i][8]][2]<<(mk[i][8]*2),c[i][8]<<mk[i][8]);
	}
	rep(i,0,6) {
		if(!c[3][i]) return;
		res<<=mk[3][i];
		res*=c[3][i];
		if(c[3][i]>=2) chk(C[c[3][i]][2]<<(mk[3][i]*2),c[3][i]<<mk[3][i]);
	}
	if(!x) return;
	cmax(ans,res*x/y);
}

void Work(int *cnt,int *mk,ll res[5][2]){
	static ll dp[2][5][2][5][5],w[5];
	int cur=0;
	memset(dp,0,sizeof dp),dp[cur][0][0][0][0]=1;
	rep(t,0,8) {
		int x=cnt[t]; ll val;
		memset(dp[!cur],0,sizeof dp[!cur]);
		rep(i,0,x) w[i]=C[x][i]<<(mk[t]*i);
		rep(i,0,4) rep(j,0,1) rep(a,0,x) rep(b,0,x-a) if((val=dp[cur][i][j][a][b])) {
			int d=a+b,y=x-d,u=min(cnt[t+1]-b,cnt[t+2]);

			rep(k,0,min(3-i,y-3,u))
				cmax(dp[!cur][i+k+1][j][b][k],val*w[d+k+3]); // 刻 + 顺

			rep(k,0,min(4-i,y,u))
				cmax(dp[!cur][i+k][j][b][k],val*w[d+k]); // 顺

			if(j) continue;
			rep(k,0,min(4-i,y-2,u))
				cmax(dp[!cur][i+k][j+1][b][k],val*w[d+k+2]); // 雀 + 顺
		}
		cur^=1;
	}
	drep(i,4,0) drep(j,1,0) if(res[i][j]) {
		rep(a,0,4-i) rep(b,0,1-j) 
			if(dp[cur][a][b][0][0]) 
				cmax(res[i+a][j+b],res[i][j]*dp[cur][a][b][0][0]);
	}
}

Pii Read(){
	static char O[5];
	scanf("%s",O);
	if(*O=='0') return mp(-1,0);
	if(isalpha(*O)) {
		if(*O=='E') return mp(3,0);
		if(*O=='S') return mp(3,1);
		if(*O=='W') return mp(3,2);
		if(*O=='N') return mp(3,3);
		if(*O=='Z') return mp(3,4);
		if(*O=='B') return mp(3,5);
		if(*O=='F') return mp(3,6);
		return mp(-1,-1);
	}
	if(O[1]=='m') return mp(0,*O-'1');
	if(O[1]=='p') return mp(1,*O-'1');
	if(O[1]=='s') return mp(2,*O-'1');
	return mp(-1,-1);
}

void Solve(){
	ans=0,memset(val,0,sizeof val),memset(mk,0,sizeof mk),val[0][0]=1;
	rep(i,0,2) rep(j,0,8) c[i][j]=4;
	rep(i,0,6) c[3][i]=4;
	while(1) {
		Pii T=Read();
		if(T.first==-1) break;
		c[T.first][T.second]--;
	}
	while(1) {
		Pii T=Read();
		if(T.first==-1) break;
		mk[T.first][T.second]=1;
	}
	Check7(),Check13();
	rep(i,0,2) Work(c[i],mk[i],val);
	rep(i,0,6) {
		static ll w[5];
		int x=c[3][i];
		rep(j,0,x) w[j]=C[x][j]<<(j*mk[3][i]);
		drep(a,4,0) drep(b,1,0) if(val[a][b]) {
			if(b<1 && x>=2) cmax(val[a][b+1],val[a][b]*w[2]); // 雀
			if(a<4 && x>=3) cmax(val[a+1][b],val[a][b]*w[3]); // 刻
			if(a<4 && x>=4) cmax(val[a+1][b],val[a][b]*w[4]); // 杠
		}
	}
	cmax(ans,val[4][1]);
	printf("%lld\n",ans);
}

int main(){
	rep(i,0,4) rep(j,C[i][0]=1,i) C[i][j]=C[i-1][j]+C[i-1][j-1];
	int T; scanf("%d",&T);
	while(T--) Solve();
}