首先，杠子是一定不比面子优的，即便杠子是宝牌，也没有合成一个面子的分值高，这意味着我们只需要考虑「$3 \times 4 + 2$」、「七对子」、「国士无双」三种和牌方式了，很显然「七对子」和「国士无双」都可以直接算出，「七对子」用优先队列直接处理，「国士无双」也可以用 $O(13^2)$ 的时间暴力算出，只剩下了一个「$3 \times 4 + 2$」不是很好算，考虑 $\rm{DP}$ 计算出最优的「$3 \times 4 + 2$」.
设 $f_{i,j,k,a,b,c}$ 表示枚举了前 $i$ 种牌，凑齐了 $j$ 对面子，$k$ 对雀头，第 $i,i+1,i+2$ 种牌的已用数量分别为 $a,b,c$ 时的最大收益
转移时考虑面子和雀头 (如 $i$ 为宝牌，则 $dora_i$ 等于 $2$ ，否则等于 $1$) ：
- 雀头转移：
$$f_{i,j,k+1,a+2,b,c}=f_{i,j,k,a,b,c}\times \frac{C_{a_i}^{k+2}}{C_{a_i}^{k}}\times dora_i^2$$
-
刻子转移：
$$f_{i,j+1,k,a+3,b,c}=f_{i,j,k,a,b,c}\times \frac{C_{a_i}^{k+3}}{C_{a_i}^{k}}\times dora_i^3$$
-
顺子转移：
$$f_{i,j+1,k,a+1,b+1,c+1}=f_{i,j,k,a,b,c}\times \frac{C_{s_i}^{a+1}}{C_{s_i}^{a}}\times \frac{C_{s_{i+1}}^{b+1}}{C_{s_{i+1}}^{b}}\times \frac{C_{s_{i+2}}^{c+1}}{C_{s_{i+2}}^{c}}\times dora_i\times dora_{i+1}\times dora_{i+2}$$
注意细节 $qwq$ .
Code:
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int T,s[40],d[40],C[5][5]={{1,0,0,0,0},{1,1,0,0,0},{1,2,1,0,0},{1,3,3,1,0},{1,4,6,4,1}};
ll ans,num[40],dp[40][6][2][6][6][6];
bool book[40]={0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1};
int special[15]={0,1,9,10,18,19,27,28,29,30,31,32,33,34};
char str[15];
int id() {
if(str[0]=='E') return 28;
else if(str[0]=='S') return 29;
else if(str[0]=='W') return 30;
else if(str[0]=='N') return 31;
else if(str[0]=='Z') return 32;
else if(str[0]=='B') return 33;
else if(str[0]=='F') return 34;
else if(str[1]=='m') return str[0]-'0';
else if(str[1]=='p') return 9+str[0]-'0';
else if(str[1]=='s') return 18+str[0]-'0';
}
priority_queue<int> q;
void Special_1() {
while(!q.empty()) q.pop();
ll res=7;
for(int i=1;i<=34;++i)
if(s[i]>=2) q.push(C[s[i]][2]*d[i]*d[i]);
if(q.size()<7) return;
for(int i=1;i<=7;++i)
res=1ll*res*q.top(),q.pop();
ans=max(ans,res);
}
void Special_2() {
for(int i=1;i<=13;++i) if(!s[special[i]]) return;
for(int i=1;i<=13;++i) {
int x=special[i];
if(s[x]<2) continue;
ll res=13ll*C[s[x]][2]*d[x]*d[x];
for(int j=1;j<=13;++j) {
if(i==j) continue;
int y=special[j];
res=1ll*res*C[s[y]][1]*d[y];
}
ans=max(ans,res);
}
}
void chkmax(ll&x,ll y) {x=max(x,y);}
void work(int i,int j,int a,int b,int c) {
if(s[i]-a>=2) chkmax(dp[i][j][1][a+2][b][c],1ll*dp[i][j][0][a][b][c]/C[s[i]
][a]*C[s[i]][a+2]*d[i]*d[i]);
if(j<4) {
if(s[i]-a>=3) for(int k=0;k<=1;++k)
chkmax(dp[i][j+1][k][a+3][b][c],1ll*dp[i][j][k][a][b][c]/C[s[i]][a]
*C[s[i]][a+3]*d[i]*d[i]*d[i]);
if(!book[i]&&s[i]-a>0&&s[i+1]-b>0&&s[i+2]-c>0) for(int k=0;k<=1;++k)
chkmax(dp[i][j+1][k][a+1][b+1][c+1],1ll*dp[i][j][k][a][b][c]/C[s[i]
][a]*C[s[i]][a+1]/C[s[i+1]][b]*C[s[i+1]][b+1]/C[s[i+2]][c]*C[s[i+2]
][c+1]*d[i]*d[i+1]*d[i+2]);
}
}
void solve() {
while(true) {scanf("%s",str);if(str[0]=='0') break;--s[id()];}
while(true) {scanf("%s",str);if(str[0]=='0') break;d[id()]=2;}
Special_1();
Special_2();
for(int i=1;i<=34;++i)
for(int j=0;j<=4;++j)
for(int a=0;a<=s[i];++a)
for(int b=0;b<=s[i+1];++b)
for(int c=0;c<=s[i+2];++c) {
if(!dp[i][j][0][a][b][c]&&!dp[i][j][1][a][b][c]) continue;
work(i,j,a,b,c);
chkmax(dp[i+1][j][0][b][c][0],dp[i][j][0][a][b][c]);
chkmax(dp[i+1][j][1][b][c][0],dp[i][j][1][a][b][c]);
if(j==4) num[i]=max(num[i],dp[i][j][1][a][b][c]);
}
for(int i=1;i<=35;++i) ans=max(ans,num[i]);
printf("%lld\n",ans);
}
void clear() {
memset(dp,0,sizeof(dp)),ans=0;
memset(num,0,sizeof(num));
for(int i=1;i<=34;++i) s[i]=4,d[i]=1;
dp[1][0][0][0][0][0]=1;
}
int main() {
scanf("%d",&T);
while(T--) clear(),solve();
return 0;
}
0 条评论