题解：P2540 [NOIP2015 提高组] 斗地主 加强版

· · 题解

题目大意

有以下几种出牌形式：


问你最少几次可以出完手牌。

注意：

思路

暴力出奇迹，考虑直接 DFS 暴力，枚举所有的方案，直接暴力出最少的次数。
暴力顺序：单顺子\to双顺子\to三顺子\to三带一\to三带二\to四带二\to四带两对\to散牌。
（这只是我的顺序，别的应该也行）。
你们可能会说，这会 TLE。
考虑剪枝优化。
只要加上

if(x>=ans) //x是当前次数，ans是最后的答案
    return;

就能减掉大部分的时间。因为当前次数已经超过了最优次数，就没必要往下搜了。
你们又要说了，还是会 TLE，没有用。
怎么办呢，我们就能使用信仰一剪。
考虑通过计数器来统计 DFS 的次数，达到一定值后退出来卡时间（我选的值是 1 \times 10^6）。

int dfn;
void dfs(int x)
{
    if(++dfn>1000000) 
        return;
...........

这样就能愉快的 AC 了。
就下来就是...

AC 代码

配合注释食用更佳。

#include<bits/stdc++.h>
using namespace std;
#define Tie ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) //快读
int T,n,ans,sum[25]; //T组数，n牌数，ans答案，sum记录牌数
int dfn; //记录dfs次数
void dfs(int x) //x记录次数
{
    if(++dfn>1000000) //剪枝优化1
        return;
    if(x>=ans) //剪枝优化2
        return;
    int k=0;
    //单顺子
    for(int i=3;i<=14;i++)
    {
        if(sum[i]==0) 
            k=0; //顺子断了,k清零
        else
        {
            k++; //顺子长度加一
            if(k>=5) //如果顺子长度大于等于5
            {
                for(int j=i-k+1;j<=i;j++) 
                    sum[j]--; //顺子中的牌数减一
                dfs(x+1); //搜下一层
                for(int j=i-k+1;j<=i;j++)  
                    sum[j]++;   //回溯
            }
        }
    }
    k=0; //清零
    //双顺子
    for(int i=3;i<=14;i++)
    {
        if(sum[i]<2) 
            k=0; //双顺子断了,k清零
        else 
        {
            k++; //双顺子长度加一
            if(k>=3) //如果双顺子长度大于等于3
            {
                for(int j=i-k+1;j<=i;j++) 
                    sum[j]-=2; //双顺子中的牌数减二
                dfs(x+1); //搜下一层
                for(int j=i-k+1;j<=i;j++) 
                    sum[j]+=2; //回溯
            }
        }
    }
    k=0;
    //三顺子
    for(int i=3;i<=14;i++)
    {
        if(sum[i]<=2) 
            k=0; //三顺子断了,k清零
        else 
        {
            k++;    //三顺子长度加一
            if(k>=2) //如果三顺子长度大于等于2
            {
                for(int j=i-k+1;j<=i;j++)
                    sum[j]-=3; //三顺子中的牌数减三
                dfs(x+1);
                for(int j=i-k+1;j<=i;j++)
                    sum[j]+=3;  //回溯
            }
        }
    }
    //以下原理同上
    for(int i=2;i<=14;i++)
    {
        if(sum[i]==3) //三带
        {
            sum[i]-=3;
            for(int j=2;j<=15;j++) //三带一
            {
                if(sum[j]<1||j==i) 
                    continue;
                sum[j]--;
                dfs(x+1);
                sum[j]++;
            }
            for(int j=2;j<=14;j++) //三带二
            {
                if(sum[j]<2||j==i) 
                    continue;
                sum[j]-=2;
                dfs(x+1);
                sum[j]+=2;
            }
            sum[i]+=3;
        } 
        if(sum[i]==4)//四带
        {
            sum[i]-=4;
            for(int j=2;j<=15;j++) //四带二
            {
                if(sum[j]<1||j==i) 
                    continue;
                sum[j]--;
                for (int k=2;k<=15;k++)
                {
                    if(sum[k]<1) 
                        continue;
                    sum[k]--;
                    dfs(x+1);
                    sum[k]++;
                }
                sum[j]++;
            }
            for(int j=2;j<=14;j++) //四带两对
            {
                if(sum[j]<2||j==i) 
                    continue;
                sum[j]-=2;
                for(int k=2;k<=14;k++) 
                {
                    if(sum[k]<2) 
                        continue;
                    sum[k]-=2;
                    dfs(x+1);
                    sum[k]+=2;
                }
                sum[j]+=2;
            }
            sum[i]+=4;
        }
    }
    for(int i=2;i<=15;i++) 
        if(sum[i]) 
            x++; //没出完的，无论是单张，对子，三张，四张都可以一次出完
    ans=min(ans,x); //更新答案
}
int main() 
{
    Tie;
    cin>>T>>n; 
    while(T--) 
    {
        dfn=0; //初始化1
        ans=INT_MAX;  //初始化2
        memset(sum,0,sizeof sum); //初始化3
        for(int i=1;i<=n;i++)
        {
            int x,y;
            cin>>x>>y;
            if(x==0) x=15; //0是大小王，算到15里
            if(x==1) x=14; //1是A，算到14里，因为A最大
            sum[x]++; //记录牌数
        }
        dfs(0); //dfs
        cout<<ans<<'\n'; //输出答案
    }
}

双倍经验: P2668 [NOIP2015 提高组] 斗地主