题解 P2668 【斗地主】

2018-07-24 15:09:16


纯属暴搜题

先处理单顺,然后双顺,三顺。

顺子处理完后,处理四带二(单,对),三带一、二

剩下的其实都一样,因为剩下的单排、对子、炸弹、三连……都只涉及一种牌,只要在dfs最后同一处理即可

另外……花色不要理他。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int T,n,ans;
int col[200];
bool shun(int x)
{
    return (col[x] && col[x+1] && col[x+2] && col[x+3] && col[(x+3)%13+1]);
}
bool liand(int x)
{
    return (col[x]>=2 && col[x+1]>=2 && col[(x+1)%13+1]>=2);
}
bool slian(int x)
{
    return (col[x]>=3 && col[x%13+1]);
}
void dfs(int dep,int num)
{
    if(dep>=ans) return;
    if(num==n)
    {
        ans=dep;
        return;
    }
    for(int i=3;i<=10;i++)
    {
        if(!shun(i)) continue;
        int k=i,cnt=1;
        col[k]--;
        while(k!=1)
        {
            cnt++,k++;
            if(k>13) k%=13;
            if(!col[k])
            {
                col[k]--;
                break;
            }
            col[k]--;
            if(cnt>=5) dfs(dep+1,num+cnt);
        }
        col[k]++;
        while(k!=i)
        {
            k--;
            if(k==0) k+=13;
            col[k]++;
        }
    }//单顺
    for(int i=3;i<=12;i++)
    {
        if(!liand(i)) continue;
        int k=i,cnt=1;
        col[k]-=2;
        while(k!=1)
        {
            cnt++,k++;
            if(k>13) k%=13;
            if(col[k]<2)
            {
                col[k]-=2;
                break;
            }
            col[k]-=2;
            if(cnt>=3) dfs(dep+1,num+2*cnt);
        }
        col[k]+=2;
        while(k!=i)
        {
            k--;
            if(k==0) k+=13;
            col[k]+=2;
        }
    }//双顺
    for(int i=3;i<=13;i++)
    {
        if(!slian(i)) continue;
        int k=i,cnt=1;
        col[k]-=3;
        while(k!=1)
        {
            cnt++,k++;
            if(k>13) k%=13;
            if(col[k]<3)
            {
                col[k]-=3;
                break;
            }
            col[k]-=3;
            if(cnt>=2) dfs(dep+1,num+3*cnt);
        }
        col[k]+=3;
        while(k!=i)
        {
            k--;
            if(k==0) k+=13;
            col[k]+=3;
        }
    }//三顺
    int k=1;
    while(k<=13)
    {
        if(col[k]==4) break;
        k++;
    }
    if(k<=13)
    {
        col[k]=0;
        for(int i=0;i<=13;i++)
            for(int j=0;j<=13;j++)
            {
                if(i==j) continue;
                if(col[i]>=2 && col[j]>=2)
                {
                    col[i]-=2,col[j]-=2;
                    dfs(dep+1,num+8);
                    col[i]+=2,col[j]+=2;
                }
                if(col[i]>=1 && col[j]>=1)
                {
                    col[i]--,col[j]--;
                    dfs(dep+1,num+6);
                    col[i]++,col[j]++;
                }
            }
        dfs(dep+1,num+4);
        col[k]=4;
    }//四带x
    k=1;
    while(k<=13)
    {
        if(col[k]>=3) break;
        k++;
    }
    if(k<=13)
    {
        col[k]-=3;
        for(int i=0;i<=13;i++)
        {
            if(col[i])
            {
                col[i]--;
                dfs(dep+1,num+4);
                col[i]++;
            }
            if(col[i]>=2)
            {
                col[i]-=2;
                dfs(dep+1,num+5);
                col[i]+=2;
            }
        }
        dfs(dep+1,num+3);
        col[k]+=3;
    }//三带x
    int tmp=0;
    for(int i=0;i<=13;i++)
        if(col[i]) tmp++;//单种牌处理
    dfs(dep+tmp,n);
}
int main()
{
    scanf("%d%d",&T,&n);
    while(T--)
    {
        ans=n;
        memset(col,0,sizeof(col));
        for(int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            col[x]++;
        }
        dfs(0,0);
        printf("%d\n",ans);
    }
    return 0;
}