「GXOI / GZOI2019」宝牌一大堆

「GXOI / GZOI2019」宝牌一大堆

麻将.jpg

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

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

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

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

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

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

暴力维护dp即可

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
",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();
}