[GXOI/GZOI2019]宝牌一大堆——DP

╰半橙微兮° 2022-01-13 04:21 194阅读 0赞

# 题目链接： #

[\[GXOI/GZOI2019\]宝牌一大堆][GXOI_GZOI2019]

求最大值容易想到$DP$，但如果将$7$种和牌都考虑进来的话，$DP$状态不好设，我们将比较特殊的七小对和国士无双单独求，其他的进行$DP$。

观察其他五种和牌可以发现，他们都是由$4$组杠子或面子和$1$组雀头组成。

那么可以列出$DP$式子：$f\[i\]\[j\]\[k\]\[l\]\[m\]\[n\]$表示前$i$种牌，其中有$j$个杠子或面子、$k$个雀头，第$i-2\\sim i$种牌分别有$l,m,n$张时前$i-3$种牌的最大值。

转移时对顺子、杠子、刻子和雀头四种情况分别转移即可。

对于国士无双，暴力枚举第$14$张牌是什么然后取最大值即可。

对于七小对，设$F\[i\]\[j\]$表示前$i$种牌中取了$j$种雀头的最大值，$01$背包转移即可。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<vector>
    #include<bitset>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int mod=1e9+7;
    ll f[35][5][2][5][5][5];
    ll F[35][8];
    char ch[3];
    int T;
    ll p[6];
    ll c[10][10];
    int s[35];
    int t[35];
    bool vis[35]={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};
    int g[20]={1,9,10,18,19,27,28,29,30,31,32,33,34};
    void add(ll &x,ll y)
    {
    	x=max(x,y);
    }
    int find(char ch[3])
    {
    	if(ch[0]=='E')return 28;
    	if(ch[0]=='S')return 29;
    	if(ch[0]=='W')return 30;
    	if(ch[0]=='N')return 31;
    	if(ch[0]=='Z')return 32;
    	if(ch[0]=='B')return 33;
    	if(ch[0]=='F')return 34;
    	if(ch[1]=='m')return ch[0]-'0';
    	if(ch[1]=='p')return 9+ch[0]-'0';
    	if(ch[1]=='s')return 18+ch[0]-'0';
    }
    ll get(int id,int num)
    {
    	return t[id]?p[num]:1ll;
    }
    ll DP()
    {
    	ll res=0;
    	memset(f,0,sizeof(f));
    	f[1][0][0][0][0][0]=1ll;
    	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)
    						{
    							ll now=f[i][j][k][l][m][n];
    							if(!now)continue;
    							if(i<34)add(f[i+1][j][k][m][n][0],now*(i>2?c[s[i-2]][l]:1)*get(i-2,l));
    							if(j<4&&s[i]-n>=3)add(f[i][j+1][k][l][m][n+3],now);
    							if(j<4&&s[i]-n>=4)add(f[i][j+1][k][l][m][n+4],now);
    							if(j<4&&vis[i]&&s[i]-n&&s[i-1]-m&&s[i-2]-l)add(f[i][j+1][k][l+1][m+1][n+1],now);
    							if(k<1&&s[i]-n>=2)add(f[i][j][k+1][l][m][n+2],now);
    							if(i==34&&j==4&&k==1)add(res,now*c[s[i]][n]*c[s[i-1]][m]*c[s[i-2]][l]*get(i,n)*get(i-1,m)*get(i-2,l));
    						}
    					}
    				}
    			}
    		}
    	}
    	return res;
    }
    ll qxd()
    {
    	memset(F,0,sizeof(F));
    	F[0][0]=1ll;
    	for(int i=1;i<=34;i++)
    	{
    		for(int j=0;j<=7;j++)
    		{
    			if(!F[i-1][j])continue;
    			add(F[i][j],F[i-1][j]);
    			if(j<7)add(F[i][j+1],F[i-1][j]*c[s[i]][2]*get(i,2));
    		}
    	}
    	return F[34][7]*7;
    }
    ll gsws()
    {
    	ll res=0;
    	for(int i=0;i<13;i++)
    	{
    		if(!s[g[i]])return 0;
    		if(s[g[i]]==1)continue;
    		ll sum=c[s[g[i]]][2]*get(g[i],2);
    		for(int j=0;j<13;j++)
    		{
    			if(i==j)continue;
    			sum=sum*s[g[j]]*get(g[j],1);
    		}
    		add(res,sum*13);
    	}
    	return res;
    }
    int main()
    {
    	for(int i=0;i<=8;i++)
    	{
    		c[i][0]=1ll;
    		for(int j=1;j<=i;j++)
    		{
    			c[i][j]=c[i-1][j]+c[i-1][j-1];
    		}
    	}
    	p[0]=1ll;
    	for(int i=1;i<=4;i++)
    	{
    		p[i]=p[i-1]*2ll;
    	}
    	scanf("%d",&T);
    	while(T--)
    	{
    		for(int i=1;i<=34;i++)
    		{
    			s[i]=4;
    		}
    		while(1)
    		{
    			scanf("%s",ch);
    			if(ch[0]=='0')break;
    			s[find(ch)]--;
    		}
    		memset(t,0,sizeof(t));
    		while(1)
    		{
    			scanf("%s",ch);
    			if(ch[0]=='0')break;
    			t[find(ch)]=1;
    		}
    		ll ans=0;
    		add(ans,DP());
    		add(ans,gsws());
    		add(ans,qxd());
    		printf("%lld\n",ans);
    	}
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10717677.html

[GXOI_GZOI2019]: https://loj.ac/problem/3084