题意

NOIP 2016 斗地主

给你一些牌，按照斗地主的出牌方式，问最少多少次出完所有的牌。

分析

这道题的做法是DFS。

为了体现这道题的锻炼效果，我自己写了好多个代码。

Ver1

直接暴力搞，加深迭代搜索。

发现出牌顺序不影响解决。

优化：先搞顺子，再搞N带N，再搞火箭，再搞N张

int DFS(int nd,int lim)
{
    int cur;
    int siz;

    if (nd>lim)
        return 0;

    siz=0;
    rep(i,3,17)
        siz+=cnt[i];
    if (nd==lim&&!siz)
        return 1;

    rep(i,3,17) if (cnt[i]>=4)
    {
        cnt[i]-=4;
        rep(j,3,17) if (cnt[j]>=1)
        {
            cnt[j]--;
            rep(k,3,17) if (cnt[k]>=1)
            {
                cnt[k]--;
                if (DFS(nd+1,lim))
                    return 1;
                cnt[k]++;
            }
            cnt[j]++;
        }
        cnt[i]+=4;
    }

    rep(i,3,14) if (cnt[i]>=3)
    {
        cur=i;
        while (cur+1<=14&&cnt[cur+1]>=3)
            cur++;
        rep(j,2,cur-i+1)
        {
            rep(k,i,i+j-1) cnt[k]-=3;
            if (DFS(nd+1,lim))
                return 1;
            rep(k,i,i+j-1) cnt[k]+=3;
        }
    }

    rep(i,3,14) if (cnt[i]>=2)
    {
        cur=i;
        while (cur+1<=14&&cnt[cur+1]>=2)
            cur++;
        rep(j,3,cur-i+1)
        {
            rep(k,i,i+j-1) cnt[k]-=2;
            if (DFS(nd+1,lim))
                return 1;
            rep(k,i,i+j-1) cnt[k]+=2;
        }
    }

    rep(i,3,14) if (cnt[i]>=1)
    {
        cur=i;
        while (cur+1<=14&&cnt[cur+1]>=1)
            cur++;
        rep(j,5,cur-i+1)
        {
            rep(k,i,i+j-1) cnt[k]--;
            if (DFS(nd+1,lim))
                return 1;
            rep(k,i,i+j-1) cnt[k]++;
        }
    }

    rep(i,3,17) if (cnt[i]>=3)
    {
        cnt[i]-=3;
        rep(j,3,17) if (cnt[j]>=2)
        {
            cnt[j]-=2;
            if (DFS(nd+1,lim))
                return 1;
            cnt[j]+=2;
        }
        cnt[i]+=3;
    }

    rep(i,3,17) if (cnt[i]>=3)
    {
        cnt[i]-=3;
        rep(j,3,17) if (cnt[j]>=1)
        {
            cnt[j]--;
            if (DFS(nd+1,lim))
                return 1;
            cnt[j]++;
        }
        cnt[i]+=3;
    }

    rep(i,3,17) if (cnt[i]>=4)
    {
        cnt[i]-=4;
        if (DFS(nd+1,lim))
            return 1;
        cnt[i]+=4;
    }

    rep(i,3,17) if (cnt[i]>=3)
    {
        cnt[i]-=3;
        if (DFS(nd+1,lim))
            return 1;
        cnt[i]+=3;
    }

    if (cnt[16]>=1&&cnt[17]>=1)
    {
        cnt[16]--,cnt[17]--;
        if (DFS(nd+1,lim))
            return 1;
        cnt[16]++,cnt[17]++;
    }

    rep(i,3,17) if (cnt[i]>=2)
    {
        cnt[i]-=2;
        if (DFS(nd+1,lim))
            return 1;
        cnt[i]+=2;
    }

    rep(i,3,17) if (cnt[i]>=1)
    {
        cnt[i]--;
        if (DFS(nd+1,lim))
            return 1;
        cnt[i]++;
    }

    return 0;
}

Ver2

在Ver1的基础上：

【优化1】

对于顺子的，原本的操作复杂度为15*15*15：

    rep(i,3,14) if (cnt[i]>=1)
    {
        cur=i;
        while (cur+1<=14&&cnt[cur+1]>=1)
            cur++;
        rep(j,5,cur-i+1)
        {
            rep(k,i,i+j-1) cnt[k]--;
            if (DFS(nd+1,lim))
                return 1;
            rep(k,i,i+j-1) cnt[k]++;
        }
    }

发现每次的操作都是重复的，所以改成15*15的操作：

    rep(i,3,14) if (cnt[i]>=1)
    {
        cur=i;
        while (cur+1<=14&&cnt[cur+1]>=1)
            cur++;
        if (cur-i+1>=5)
        {
            rep(j,i,cur) cnt[j]--;
            per(j,cur,i+4)
            {
                if (j!=cur) cnt[j+1]++;
                if (DFS(nd+1,lim))
                    return 1;
            }
            rep(j,i,i+4) cnt[j]++;
        }
    }

Ver3

改成深搜+剪枝，加一个dwl属性。

枚举完所有的第一种才能枚举第二种，枚举完所有的第二种才能枚举第三种，etc。

void DFS(int nd,int dwl)
{
    int cur;
    int siz;

    if (nd>=ans)
        return;

    siz=0;
    rep(i,3,17)
        siz+=cnt[i];
    if (!siz)
    {
        ans=nd;
        return;
    }

     //①先per优化一个*5
     //②改变顺序
    if (dwl<=1)
    {
        if (cnt[16]>=1&&cnt[17]>=1)
        {
            cnt[16]--,cnt[17]--;
            DFS(nd+1,1);
            cnt[16]++,cnt[17]++;
        }
    }
    //火箭 

    if (dwl<=2)
    {
        rep(i,3,14) if (cnt[i]>=1)
        {
            cur=i;
            while (cur+1<=14&&cnt[cur+1]>=1)
                cur++;
            if (cur-i+1>=5)
            {
                rep(j,i,cur) cnt[j]--;
                per(j,cur,i+4)
                {
                    if (j!=cur) cnt[j+1]++;
                    DFS(nd+1,2);
                }
                rep(j,i,i+4) cnt[j]++;
            }
        }
    }
    //单顺子 

    if (dwl<=3)
    {
        rep(i,3,14) if (cnt[i]>=3)
        {
            cur=i;
            while (cur+1<=14&&cnt[cur+1]>=3)
                cur++;
            if (cur-i+1>=2)
            {
                rep(j,i,cur) cnt[j]-=3;
                per(j,cur,i+1)
                {
                    if (j!=cur) cnt[j+1]+=3;
                    DFS(nd+1,3);
                }
                rep(j,i,i+1) cnt[j]+=3;
            }
        }
    }
    //三顺子 

    if (dwl<=4)
    {
        rep(i,3,14) if (cnt[i]>=2)
        {
            cur=i;
            while (cur+1<=14&&cnt[cur+1]>=2)
                cur++;
            if (cur-i+1>=3)
            {
                rep(j,i,cur) cnt[j]-=2;
                per(j,cur,i+2)
                {
                    if (j!=cur) cnt[j+1]+=2;
                    DFS(nd+1,4);
                }
                rep(j,i,i+2) cnt[j]+=2;
            }
        }
    }
    //双顺子 

    if (dwl<=5)
    {
        rep(i,3,17) if (cnt[i]>=4)
        {
            cnt[i]-=4;
            rep(j,3,17) if (cnt[j]>=1)
            {
                cnt[j]--;
                rep(k,j,17) if (cnt[k]>=1)
                {
                    cnt[k]--;
                    DFS(nd+1,5);
                    cnt[k]++;
                }
                cnt[j]++;
            }
            cnt[i]+=4;
        }
    }
    //四带二

    if (dwl<=6)
    {
        rep(i,3,17) if (cnt[i]>=3)
        {
            cnt[i]-=3;
            rep(j,3,17) if (cnt[j]>=2)
            {
                cnt[j]-=2;
                DFS(nd+1,6);
                cnt[j]+=2;
            }
            cnt[i]+=3;
        }
    }
    //三带二 

    if (dwl<=7)
    {
        rep(i,3,17) if (cnt[i]>=3)
        {
            cnt[i]-=3;
            rep(j,3,17) if (cnt[j]>=1)
            {
                cnt[j]--;
                DFS(nd+1,7);
                cnt[j]++;
            }
            cnt[i]+=3;
        }
    }
    //三带一 

    if (dwl<=8)
    {
        rep(i,3,17) if (cnt[i]>=4)
        {
            cnt[i]-=4;
            DFS(nd+1,8);
            cnt[i]+=4;
        }
    }
    //炸弹 

    if (dwl<=9)
    {
        rep(i,3,17) if (cnt[i]>=3)
        {
            cnt[i]-=3;
            DFS(nd+1,9);
            cnt[i]+=3;
        }
    }
    //三张牌 

    if (dwl<=10)
    {
        rep(i,3,17) if (cnt[i]>=2)
        {
            cnt[i]-=2;
            DFS(nd+1,10);
            cnt[i]+=2;
        }
    }
    //对牌 

    if (dwl<=11)
    {
        rep(i,3,17) if (cnt[i]>=1)
        {
            cnt[i]--;
            DFS(nd+1,11);
            cnt[i]++;
        }
    }
    //单牌
}

Ver4

忘记自己干了啥了。。

Ver5

始终是30ptTLE掉。

所以直接看正解了。

http://blog.csdn.net/xieguofu2014/article/details/50193545

既然有正解了，这里就不再写了。

关键在于把操作进行一下分类：顺子、N带N，然后归纳通性。

附网上的STD（含自己乱七八糟的注释）：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>

typedef long long ll;
typedef double lf;

const int INF=1<<30;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int T,n,ans;
struct state{
    int num[16];
    inline int& operator[](int x){return num[x];}
}now;
int temp[10];

void dfs(int);
void group(int c,int s,int depth)
//个数为c，至少要有s个，当前已经进行了depth次
{
    for(int st=1,fi;st<=12-s+1;st++){
        for(fi=st;now[fi]>=c&&fi<=12;fi++){
            now[fi]-=c;
            if(fi-st+1>=s)
                dfs(depth+1);
        }
        for(int i=st;i<fi;i++)
            now[i]+=c;
    }
    //暴力剪
}

void dfs(int depth){
    if(depth>ans)return;
    //剪！！ 

    int sum=0;
    for(int i=1;i<=15;i++)
        temp[now[i]]++;
    //temp[i]: now[j]=i的个数 

    while(temp[4]>0){
        temp[4]--,sum++;
        //4张直接出
        if(temp[2]>=2)
            temp[2]-=2;
        else if(temp[1]>=2)
            temp[1]-=2;
    }
    //四带二 

    while(temp[3]>0){
        temp[3]--,sum++;
        if(temp[2]>=1)
            temp[2]--;
        else if(temp[1]>=1)
            temp[1]--;
    }
    //三带 

    sum+=temp[1]+temp[2];
    //一和二直接 

    if(temp[1]>=2&&now[14]>=1&&now[15]>=1)
        sum--;
    //处理JOKER的情况：sum-- 

    temp[1]=temp[2]=0;
    if(depth+sum<ans)
        ans=depth+sum;
    //若depth+sum<ans那么就更新

    //上面一大段，解决的是：昨晚所有的顺子之后，直接贪心求解的情况 

    group(1,5,depth);
    //枚举单张，长度为5的单顺子
    group(2,3,depth);
    //枚举双张，长度为3的双顺子
    group(3,2,depth);
    //枚举3张，长度为2的三顺子
}

void work(){
    memset(now.num,0,sizeof now.num);
    ans=1<<30;
    for(int i=1;i<=n;i++){
        int k=read(),c=read();
        if(k==0)
            now[13+c]++;
        else if(k<=2)
            now[11+k]++;
        else
            now[k-2]++;
    }
    dfs(0);
    printf("%d\n",ans);
}

int main(){
    freopen("a.in","r",stdin);
    freopen("a.ans","w",stdout);
    T=read(),n=read();
    for(int turn=1;turn<=T;turn++)
        work();
    return 0;
}

附自己的AC代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <climits>
#include <algorithm>
using namespace std;

#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)

const int MAX=INT_MAX;

int cas;

int n;
int cnt[16];

int ans;
int cal[5];

inline int rd(void)
{
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

int Calc(void)
{
    int sum=0;

    memset(cal,0,sizeof cal);
    rep(i,1,15)
        cal[cnt[i]]++;

    while (cal[4]>0)
    {
        sum++; cal[4]--;
        if (cal[2]>=2)
            cal[2]-=2;
        else if (cal[1]>=2)
            cal[1]-=2;
    }

    while (cal[3]>0)
    {
        sum++; cal[3]--;
        if (cal[2]>=1)
            cal[2]--;
        else if (cal[1]>=1)
            cal[1]--;
    }

    sum+=(cal[2]+cal[1]);

    if (cal[1]>=2&&cnt[14]>=1&&cnt[15]>=1)
        sum--;

    return sum;
}

void DFS(int);
void Solve(int c,int len,int dep)
{
    int cur;
    rep(i,1,12-len+1) if (cnt[i]>=c)
    {
        cur=i;
        while (cur+1<=12&&cnt[cur+1]>=c)
            cur++;
        if (cur-i+1>=len)
        {
            rep(j,i,cur) cnt[j]-=c;
            per(j,cur,i+len-1)
            {
                if (j!=cur) cnt[j+1]+=c;
                DFS(dep+1);
            }
            rep(j,i,i+len-1) cnt[j]+=c;
        }
    }
}

void DFS(int dep)
{
    if (dep>ans)
        return;

    int sum=Calc();
    ans=min(ans,sum+dep);

    Solve(1,5,dep);
    Solve(2,3,dep);
    Solve(3,2,dep);
}

int main(void)
{
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);

    cas=rd(),n=rd();
    rep(tur,1,cas)
    {
        int x,y; memset(cnt,0,sizeof cnt);
        rep(i,1,n)
        {
            x=rd(),y=rd();
            if (0<x&&x<=2) cnt[x+11]++;
            else if (x>2) cnt[x-2]++;
            else cnt[y+13]++;
        }

        ans=MAX;
        DFS(0);
        printf("%d\n",ans);
    }

    return 0;
}

小结

（1）对于操作很多很繁杂的问题时，分类的作用必不可少。

分类的目的在于：限定具有相同结构的一些对象，研究它们的通性，更好地优化问题。

本题就是按照顺子、N带N这两个来分类，先处理完所有的顺子，N带N的就可以贪心了。

其实这种东西在化学课上才刚讲完，为什么想不出来，真的应该好好反思一下。

（2）当操作顺序不影响的时候，我们的想法是定序：规定枚举顺序。即：必然从前面枚举到后面，减少一个数量级。

其实最后的代码并没有使用定序的优化，但是优化后效果更佳。