题解 P5301 [GXOI/GZOI2019]宝牌一大堆

genshy · 2021-03-31 21:49:03 · 题解

动态规划（传说中的麻将类dp）。

简化题意：给你一些已经使用过的牌，让你从没使用过的牌中选出一组能够胡牌的组合，问这个组合的最大达成分数为多少。

首先考虑一个问题就是杠子是没有刻子要优的。因为 {4\choose 1} < {4\choose 3}， 也就是说当你选了杠子的时候，舍弃一张牌让其变成刻子是要更优的。

然后我们的胡牌方式就变成了三种：七对子，国土无双，3\times 4+2 。

分三种情况讨论一下：

第一种情况：七对子胡牌

这种情况很好处理，只需要开个堆，维护每种牌组成雀头的最大价值。取堆中前 7 大的即可。

第二种情况：国土无双胡牌

枚举那一种牌出现了两次，算一下每种情况的答案，最后在取个 \min 即可。

复杂度：O(13^2) 。

第三种情况：3\times 4+2

这种情况就比较难处理了，考虑用 dp 来解决这个问题。

设 f(i,j,k,u,v,w) (k\in \{0,1\}) 表示前 i 种牌，组成 j 对面子，k 对雀头，其中第 i,i+1,i+2 分别选了 u,v,w 张的最大价值。

分 刻子/顺子/雀头/直接转移四种情况考虑。

• 直接转移：

  f(i+1,j,k,0,v,w) = f(i,j,k,u,v,w)

• 雀头：

  f(i,j,k+1,u+2,v,w) = f(i,j,k,u,v,w)\times {{num[i]\choose u+2}\over {num[i]\choose u}}\times (good[i])^2

  中间拿两个组合数相除的意思为先把 i 在 f(i,j,k,u,v,w) 中的贡献 num[i]\choose u 除去，在算上其在 f(i,j,k,u+2,v,w) 的贡献 num[i]\choose u+2 。(good[i])^2 则算的是新加入的两张 i 类型的牌的宝牌分数。

• 刻子：

  f(i,j+1,k,u+3,v,w) = f(i,j,k,u,v,w)\times {{num[i]\choose u+3}\over {num[i]\choose u}}\times (good[i])^3

  这个其实和上面雀头的转移是类似的。

• 顺子：

  f(i,j+1,k,u+1,v+1,w+1) = f(i,j,k,u,v,w)\times {{num[i]\choose u+1}\over {num[i]\choose u}}\times {{num[i+1]\choose v+1}\over {num[i+1]\choose v}}\times {{num[i+2]\choose w+1}\over {num[i+2]\choose w}} \times good[i]\times good[i+1]\times good[i+2]

  和上面的刻子的转移时类似的，就是考虑先把 i,i+1,i+2 在 f(i,j,k,u,v,w) 乘上的组合数除去，在乘上其在 f(i,j+1,k,u+1,v+1,w+1) 的组合数，同时在算上选 i,i+1,i+2 的宝牌分数即可

然后这样我们就可以直接暴力 dp 了，复杂度：O(T\times 34\times 2\times 4^4) 。

这样只能得到 60pts 的分数。

考虑优化一下，其实当 f(i,j,k,u,v,w) = 0 的时候，我们是没必要用它来进行转移的.

用这个优化就可以省去不少无用状态,然后这道题就可以过了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define int long long
int T,ans,c[50][50],num[50],good[50],f[36][5][2][5][5][5];
int a[50] = {0,1,9,10,18,19,27,28,29,30,31,32,33,34};
bool can[50] = {0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0};
char s[5];
void YYCH()
{
    c[0][0] = 1;
    for(int i = 1; i <= 4; i++)
    {
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; j++)
        {
            c[i][j] = c[i-1][j] + c[i-1][j-1];
        }
    }
}
int bianhao(char s[3])
{
    if(s[1] >= '0' && s[1] <= '9')
    {
        if(s[2] == 'm') return s[1] - '0';
        if(s[2] == 'p') return 9 + s[1] - '0';
        if(s[2] == 's') return 18 + s[1] - '0';
    }   
    if(s[1] == 'E') return 28;
    if(s[1] == 'S') return 29;
    if(s[1] == 'W') return 30;
    if(s[1] == 'N') return 31;
    if(s[1] == 'Z') return 32; 
    if(s[1] == 'B') return 33;
    if(s[1] == 'F') return 34;
}
int C(int x,int y){return c[x][y];}
int Qiduizi()
{
    priority_queue<int> q;
    for(int i = 1; i <= 34; i++)
    {
        if(num[i] >= 2) q.push(C(num[i],2)*good[i]*good[i]);
    }
    if(q.size() < 7) return 0;
    int res = 1, cnt = 0;
    while(cnt < 7) cnt++, res *= q.top(), q.pop();
    return res*7;
}
int Guotuwushuang()
{
    for(int i = 1; i <= 13; i++) if(!num[a[i]]) return 0;
    int ans = 0;
    for(int i = 1; i <= 13; i++)
    {
        int res = 13 * C(num[a[i]],2) * good[a[i]] * good[a[i]];
        for(int j = 1; j <= 13; j++) if(j != i) res = res * C(num[a[j]],1) * good[a[j]];
        ans = max(ans,res);
    }
    return ans;
}
int dp()
{
    memset(f,0,sizeof(f));//前i张牌，j对面子，k对雀头，第i,i+1,i+2 的牌的数量的最大价值。
    f[1][0][0][0][0][0] = 1;
    for(int i = 1; i <= 34; i++)
    {
        for(int j = 0; j <= 4; j++)
        {
            for(int k = 0; k <= 1; k++)
            {
                for(int u = 0; u <= 4; u++)
                {
                    for(int v = 0; v <= 4; v++)
                    {
                        for(int w = 0; w <= 4; w++)
                        {
                            if(!f[i][j][k][u][v][w]) continue;
                            if(k == 0 && u+2 <= num[i]) f[i][j][1][u+2][v][w] = max(f[i][j][1][u+2][v][w],f[i][j][k][u][v][w]/C(num[i],u)*C(num[i],u+2)*good[i]*good[i]);
                            if(j+1 <= 4 && u+3 <= num[i]) f[i][j+1][k][u+3][v][w] = max(f[i][j+1][k][u+3][v][w],f[i][j][k][u][v][w]/C(num[i],u)*C(num[i],u+3)*good[i]*good[i]*good[i]);
                            if(j+1 <= 4 && can[i] && u+1 <= num[i] && v+1 <= num[i+1] && w+1 <= num[i+2]) f[i][j+1][k][u+1][v+1][w+1] = max(f[i][j+1][k][u+1][v+1][w+1],f[i][j][k][u][v][w]/C(num[i],u)*C(num[i],u+1)/C(num[i+1],v)*C(num[i+1],v+1)/C(num[i+2],w)*C(num[i+2],w+1)*good[i]*good[i+1]*good[i+2]); 
                            if(i <= 34) f[i+1][j][k][v][w][0] = max(f[i+1][j][k][v][w][0],f[i][j][k][u][v][w]);
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= 34; i++)
    {
        for(int j = 0; j <= 4; j++)
        {
            for(int k = 0; k <= 4; k++)
            {
                for(int u = 0; u <= 4; u++)
                {
                    ans = max(ans,f[i][4][0][j][k][u]);
                    ans = max(ans,f[i][4][1][j][k][u]);
                }
            }
        }
    }
    return ans;
}
signed main()
{
    scanf("%d",&T); YYCH();
    while(T--)
    {
        ans = 0;
        for(int i = 1; i <= 34; i++) num[i] = 4, good[i] = 1;
        while(scanf("%s",s+1) != EOF && s[1] != '0') num[bianhao(s)]--;
        while(scanf("%s",s+1) != EOF && s[1] != '0') good[bianhao(s)] = 2;
        ans = max(ans,Guotuwushuang());
        ans = max(ans,Qiduizi());
        ans = max(ans,dp());
        printf("%lld\n",ans);
    } 
    return 0;
}