[洛谷 5301,loj 3084][GXOI/GZOI2019]宝牌一大堆

题目链接

https://www.luogu.org/problem/P5301

https://loj.ac/problem/3084

题解

话说现在出题人怎么这么喜欢麻将啊,报警了 QAQ

这是一道非常考验码力的线性 DP 题…窝参考了一下官方题解的思路。

国士无双和七对子这两种特殊的牌型都可以直接算:国士无双因为胡的牌的种类都是确定的,直接算分数即可;七对子只需贪心取分数最高的 7 对牌。

剩下的牌型其实特点都一样:4 组面子(取杠子分数由于方案数变少一定不优)+1对雀头。

我们设 \(f(i,j,k,l,m,n)\) 表示处理到第 \(i\) 种牌,有 \(j\) 组面子,\(k\) 组雀头,使用 \(l\) 张 \(i-2\) 种类的牌,\(m\) 张 \(i-1\) 种类的牌和 \(n\) 张 \(i\) 种类的牌,前 \(i-3\) 种牌的最大价值。

显然有以下限制:\(j \leq 4, k \leq 1, l,m,n \leq 4\)。

每次有以下几种决策:

  1. 跳到下一种牌;
  2. 做一组刻子;
  3. 做一组顺子;
  4. 做一对雀头。

需要注意以下不合法转移:

  1. 牌不够用(剩下的牌不够形成一组刻子/杠子/顺子/雀头);
  2. 有些牌无法组成顺子:例如风牌和三元牌,以及不存在以 \(1,2\) 结尾的顺子牌;
  3. 雀头有且只有一对,所以已经有雀头的时候就不要再加了。

下面是程序(转移的时候用了刷表法):

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int gs[]={0,1,9,10,18,19,27,28,29,30,31,32,33,34};
const int shunzi[]={0,0,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};
long long c[5][5],re[35],dora[35],f[35][5][5][5][5][5],qd[35];
char s[5];
bool cmp(int a,int b)
{
 return a>b;
}
long long calc_gsws()
{
 long long ans=0;
 for(int i=1;i<=13;i++)
 {
  long long res=1;
  for(int j=1;j<=13;j++)
   if(i==j)
   {
    if(re[gs[j]]<2)res=0;
    else res*=c[re[gs[j]]][2]*(dora[gs[j]]?4:1);
   }
   else
   {
    if(re[gs[j]]<1)res=0;
    else res*=re[gs[j]]*(dora[gs[j]]?2:1);
   }
  ans=max(ans,res);
 }
 return ans*13;
}
long long calc_qd()
{
 for(int i=1;i<=34;i++)
  if(re[i]>=2)qd[i]=c[re[i]][2]*(dora[i]?4:1);
 sort(qd+1,qd+35,cmp);
 long long ans=1;
 for(int i=1;i<=7;i++)
  ans*=qd[i];
 return ans*7;
}
int main()
{
 int t;
 cin>>t;
 c[0][0]=1;
 for(int i=1;i<=4;i++)
 {
  c[i][0]=1;
  for(int j=1;j<=4;j++)
   c[i][j]=c[i-1][j]+c[i-1][j-1];
 }
 while(t--)
 {
  for(int i=1;i<=34;i++)
   re[i]=4;
  memset(dora,0,sizeof(dora));
  memset(f,0,sizeof(f));
  memset(qd,0,sizeof(qd));
  while(1)
  {
   cin>>s;
   int x=s[0]-'0';
   if(s[0]=='0')break;
   else if(s[0]=='E')re[28]--;
   else if(s[0]=='S')re[29]--;
   else if(s[0]=='W')re[30]--;
   else if(s[0]=='N')re[31]--;
   else if(s[0]=='Z')re[32]--;
   else if(s[0]=='B')re[33]--;
   else if(s[0]=='F')re[34]--;
   else if(s[1]=='m')re[x]--;
   else if(s[1]=='p')re[9+x]--;
   else re[18+x]--;
  }
  while(1)
  {
   cin>>s;
   int x=s[0]-'0';
   if(s[0]=='0')break;
   else if(s[0]=='E')dora[28]++;
   else if(s[0]=='S')dora[29]++;
   else if(s[0]=='W')dora[30]++;
   else if(s[0]=='N')dora[31]++;
   else if(s[0]=='Z')dora[32]++;
   else if(s[0]=='B')dora[33]++;
   else if(s[0]=='F')dora[34]++;
   else if(s[1]=='m')dora[x]++;
   else if(s[1]=='p')dora[9+x]++;
   else dora[18+x]++;
  }
  long long ans=max(calc_gsws(),calc_qd());
  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 l=0;l<=4;l++)
      for(int m=0;m<=4;m++)
       for(int n=0;n<=4;n++)
       {
        long long cur=f[i][j][k][l][m][n];
        if(!cur)continue;
        if(i<34)f[i+1][j][k][m][n][0]=max(f[i+1][j][k][m][n][0],cur*(i>2?c[re[i-2]][l]:1)*(1<<(l*dora[i-2])));
        if(j<4&&re[i]-n>=3)f[i][j+1][k][l][m][n+3]=max(f[i][j+1][k][l][m][n+3],cur);
        if(j<4&&re[i]-n>=4)f[i][j+1][k][l][m][n+4]=max(f[i][j+1][k][l][m][n+4],cur);
        if(j<4&&shunzi[i]&&re[i]-n&&re[i-1]-m&&re[i-2]-l)f[i][j+1][k][l+1][m+1][n+1]=max(f[i][j+1][k][l+1][m+1][n+1],cur);
        if((!k)&&re[i]-n>=2)f[i][j][k+1][l][m][n+2]=max(f[i][j][k+1][l][m][n+2],cur);
        if(i==34&&j==4&&k==1)ans=max(ans,cur*c[re[i]][n]*c[re[i-1]][m]*c[re[i-2]][l]*(1<<(n*dora[i]))*(1<<(m*dora[i-1]))*(1<<(l*dora[i-2])));
       }
  cout<<ans<<endl;
 }
 return 0;
}

发表回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据