首先,杠子是一定不比面子优的,即便杠子是宝牌,也没有合成一个面子的分值高,这意味着我们只需要考虑「$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;
}
分类: 文章

Qiuly

井戸の底の空にはまだかすかな希望の光がある……

发表评论

电子邮件地址不会被公开。 必填项已用*标注