[GXOI/GZOI2019]宝牌一大堆

时间:2022-01-09 19:01:19

感觉比ZJOI的麻将要休闲很多啊。

这个题就是一个最优化问题,没有面子的特殊牌型可以直接用复杂度较低的贪心判掉。

有面子的话就是一个经典dp。(曾经还在ZJOI写过这个毒瘤东西

大概就是存一下对子,面子,杠子的个数,再记一下上两个位置剩余的牌的个数,转移非常简单。

写起来挺爽的。

#include<bits/stdc++.h>
#define N 55
#define eps 1e-7
#define inf 1e18+7
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline ll read()
{
char ch=0;
ll x=0,flag=1;
while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*flag;
}
map<string,ll>mp;
bool h[N],flag[N],chk[N][N][N];
ll tot,ans,a[N],b[N],cnt[N],C[N][N];
void prepare()
{
//万
mp["1m"]=++tot;mp["2m"]=++tot;mp["3m"]=++tot;
mp["4m"]=++tot;mp["5m"]=++tot;mp["6m"]=++tot;
mp["7m"]=++tot;mp["8m"]=++tot;mp["9m"]=++tot;
//筒
mp["1p"]=++tot;mp["2p"]=++tot;mp["3p"]=++tot;
mp["4p"]=++tot;mp["5p"]=++tot;mp["6p"]=++tot;
mp["7p"]=++tot;mp["8p"]=++tot;mp["9p"]=++tot;
//索
mp["1s"]=++tot;mp["2s"]=++tot;mp["3s"]=++tot;
mp["4s"]=++tot;mp["5s"]=++tot;mp["6s"]=++tot;
mp["7s"]=++tot;mp["8s"]=++tot;mp["9s"]=++tot;
//其它
mp["E"]=++tot;mp["S"]=++tot;mp["W"]=++tot;mp["N"]=++tot;
mp["Z"]=++tot;mp["B"]=++tot;mp["F"]=++tot;
//组合数
for(ll i=0;i<=10;i++)
{
C[i][0]=1;
for(ll j=1;j<=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
}
//预处理可以凑面子的位置
for(ll i=1;i<=27;i++)h[i]=true;
h[1]=h[2]=h[10]=h[11]=h[19]=h[20]=false;
//预处理合法状态
chk[1][4][0]=chk[1][3][1]=chk[1][2][2]=chk[1][1][3]=true;
for(ll i=1;i>=0;i--)for(ll j=4;j>=0;j--)for(ll k=4;k>=0;k--)
if(chk[i][j][k])
{
if(i)chk[i-1][j][k]=true;
if(j)chk[i][j-1][k]=true;
if(k)chk[i][j][k-1]=true;
}
}
void clear()
{
ans=0;
for(ll i=0;i<=4;i++)a[i]=b[i]=0;
for(ll i=1;i<=tot;i++)cnt[i]=4,flag[i]=false;
}
ll ksm(ll x,ll k)
{
ll ans=1;
while(k){if(k&1)ans*=x;k>>=1;x*=x;}
return ans;
}
ll work1()//七对子
{
ll k,now=0,ans=7;
k=min(a[4],7-now);now+=k;ans*=ksm(24,k);
k=min(a[3],7-now);now+=k;ans*=ksm(12,k);
k=min(b[4],7-now);now+=k;ans*=ksm(6,k);
k=min(a[2],7-now);now+=k;ans*=ksm(4,k);
k=min(b[3],7-now);now+=k;ans*=ksm(3,k);
k=min(b[2],7-now);now+=k;ans*=ksm(1,k);
k=min(a[4],7-now);now+=k;ans/=ksm(6,k);ans*=ksm(4,k);
k=min(b[4],7-now);now+=k;ans/=ksm(6,k);ans*=ksm(1,k);
if(now==7)return ans;else return -inf;
}
ll work2()//国士无双
{
bool ok=false;
ll p[20],now=13,ans=0;
p[1]=1;p[2]=9;p[3]=10;p[4]=18;p[5]=19;p[6]=27;
p[7]=28;p[8]=29;p[9]=30;p[10]=31;p[11]=32;p[12]=33;p[13]=34;
for(ll i=1;i<=13;i++)
{
ll x=p[i];
if(!cnt[x])return -inf;
if(cnt[x]>=2)ok=true;
now*=cnt[x];if(flag[x])now*=2;
}
if(!ok)return -inf;
for(ll i=1;i<=13;i++)
{
ll x=p[i];
if(cnt[x]==2)ans=max(ans,(now/2)*1*(flag[x]?2:1));
if(cnt[x]==3)ans=max(ans,(now/3)*3*(flag[x]?2:1));
if(cnt[x]==4)ans=max(ans,(now/4)*6*(flag[x]?2:1));
}
return ans;
}
ll dp[2][5][4][5][5][5],DP[2][5][4][5][5][5];
void update(ll &x,ll k){x=max(x,k);}
ll work3()//各种杠子+面子+雀头
{
memset(DP,-1,sizeof(DP));
DP[0][0][0][cnt[1]][0][0]=1;
for(ll i=1;i<=tot;i++)
{
ll lx=cnt[i],ly=(i<=1)?0:cnt[i-1],lz=(i<=2)?0:cnt[i-2];
for(ll a=0;a<=1;a++)for(ll b=0;b<=4;b++)for(ll c=0;c<=3;c++)if(chk[a][b][c])
for(ll x=0;x<=4;x++)for(ll y=0;y<=4;y++)for(ll z=0;z<=4;z++)
dp[a][b][c][x][y][z]=DP[a][b][c][x][y][z],DP[a][b][c][x][y][z]=-1; for(ll a=0;a<=1;a++)for(ll b=0;b<=4;b++)for(ll c=0;c<=3;c++)if(chk[a][b][c])
for(ll x=0;x<=lx;x++)for(ll y=0;y<=ly;y++)for(ll z=0;z<=lz;z++)
{
ll o=dp[a][b][c][x][y][z];if(o<=0)continue;
if(x>=2&&a!=1)update(dp[a+1][b][c][x-2][y][z],o);
if(x>=3&&b!=4)update(dp[a][b+1][c][x-3][y][z],o);
if(x>=4&&c!=3)update(dp[a][b][c+1][x-4][y][z],o);
if(x&&y&&z&&b!=4&&h[i])update(dp[a][b+1][c][x-1][y-1][z-1],o);
if(i<=2)update(DP[a][b][c][cnt[i+1]][x][y],o);
else
{
ll k=cnt[i-2]-z;
o*=C[cnt[i-2]][k]*(flag[i-2]?ksm(2,k):1);
update(DP[a][b][c][cnt[i+1]][x][y],o);
}
}
}
ll ans=0;
for(ll a=0;a<=1;a++)for(ll b=0;b<=4;b++)for(ll c=0;c<=3;c++)if(chk[a][b][c])
for(ll x=0;x<=cnt[tot-0];x++)for(ll y=0;y<=cnt[tot-1];y++)for(ll z=0;z<=cnt[tot-2];z++)
{
ll ka=cnt[tot-0]-x,kb=cnt[tot-1]-y,kc=cnt[tot-2]-z;
dp[a][b][c][x][y][z]*=C[cnt[tot-0]][ka]*(flag[tot-0]?ksm(2,ka):1);
dp[a][b][c][x][y][z]*=C[cnt[tot-1]][kb]*(flag[tot-1]?ksm(2,kb):1);
dp[a][b][c][x][y][z]*=C[cnt[tot-2]][kc]*(flag[tot-2]?ksm(2,kc):1);
if(a==1&&b==4&&c==0)ans=max(ans,dp[a][b][c][x][y][z]);
if(a==1&&b==3&&c==1)ans=max(ans,dp[a][b][c][x][y][z]);
if(a==1&&b==1&&c==3)ans=max(ans,dp[a][b][c][x][y][z]);
if(a==1&&b==4&&c==0)ans=max(ans,dp[a][b][c][x][y][z]);
}
return ans;
}
ll work4()//特殊处理4杠子+1对子
{
ll ans=-inf;
for(ll i=2;i<=4;i++)if(a[i])
{
a[i]--;
ll k,v=4*C[i][2],now=0;
k=min(a[4],4-now);now+=k;v*=ksm(16,k);
k=min(b[4],4-now);now+=k;v*=ksm(1,k);
if(now==4)ans=max(ans,v);
a[i]++;
}
for(ll i=2;i<=4;i++)if(b[i])
{
b[i]--;
ll k,v=1*C[i][2],now=0;
k=min(a[4],4-now);now+=k;v*=ksm(16,k);
k=min(b[4],4-now);now+=k;v*=ksm(1,k);
if(now==4)ans=max(ans,v);
b[i]++;
}
return ans;
}
void solve()
{
clear();
while(true)
{
string s;cin>>s;
if(s[0]=='0')break;
cnt[mp[s]]--;
}
while(true)
{
string s;cin>>s;
if(s[0]=='0')break;
flag[mp[s]]=true;
}
for(ll i=1;i<=tot;i++)if(flag[i])a[cnt[i]]++;else b[cnt[i]]++;
ans=max(ans,work1());ans=max(ans,work2());ans=max(ans,work3());ans=max(ans,work4());
printf("%lld\n",ans);
}
int main()
{
prepare();
ll t=read();
for(ll i=1;i<=t;i++)solve();
return 0;
}