[NOIP2015] 斗地主

 

    有这一张图片就够了，原来考虑用状压，但会超时。。所以果断大暴搜。。→ _→

    率先搜顺子，三，四带几，注：四个二带俩王，四个A带对二加对二，都是非法的。。

    走牌快的弄完后，把单出4,3,2,1一次性加上。

    改这道题时，机房里有一群人在喊“俩王”，“仨四带二”。。感觉真有人在玩。。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,ans=100000;
struct pai
{
    int f[20];
}a;
int read()
{
    int sum=0,f=1;char x=getchar();
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9')sum=sum*10+x-'0',x=getchar();
    return sum*f;
}
int check(int x,pai b,int len)
{
    int s=0;
    for(int i=x;i<13;i++)
       if(b.f[i]>=len)
         s++;
       else
          break;
    return s;
}
void dfs(int len,pai x,int sum)
{
    if(len==0)
    {
        ans=min(ans,sum);
        return;
    }
    pai b=x;
    for(int i=1;i<13;i++)
    if(x.f[i]>0)
    {
       int k=check(i,x,1);
       if(k<5)continue;
       for(int j=0;j<k;j++)
           b.f[i+j]--;
       // cout<<"shunzi"<<k<<" "<<i<<" "<<sum<<" "<<len<<endl;
       dfs(len-k,b,sum+1);
       b=x;
    }
    for(int i=1;i<13;i++)
    if(x.f[i]>1)
    {
       int k=check(i,x,2);
       if(k<3)continue;
       for(int j=0;j<k;j++)
           b.f[i+j]-=2;
       dfs(len-k*2,b,sum+1);
       b=x;
    }
    for(int i=1;i<13;i++)
    if(x.f[i]>2)
    {
       int k=check(i,x,3);
       if(k<3){
          continue;
        }
       for(int j=0;j<k;j++)
           b.f[i+j]-=3;
       dfs(len-k*3,b,sum+1);
       b=x;
    }
    for(int i=0;i<13;i++)
    if(x.f[i]==4)
        for(int j1=0;j1<13;j1++)
           if(j1!=i&&x.f[j1]>0)
              for(int j2=0;j2<13;j2++)
                 if(j2!=i&&j2!=j1&&x.f[j2]>0)
                 {
                    b.f[i]-=4;
                    b.f[j1]--;b.f[j2]--;
                    dfs(len-6,b,sum+1);
                    b=x;
                    if(b.f[j1]>=2&&b.f[j2]>=2)
                    {
                        b.f[i]-=4;
                        b.f[j1]-=2;b.f[j2]-=2;
                        dfs(len-8,b,sum+1);
                        b=x;
                    }
                 }
    for(int i=0;i<13;i++)
    if(x.f[i]>=3)
        for(int j1=0;j1<13;j1++)
           if(j1!=i&&x.f[j1]>0)
           {
                b.f[i]-=3;
                b.f[j1]--;
                dfs(len-4,b,sum+1);
                b=x;
                if(b.f[j1]>=2)
                {
                    b.f[i]-=3;
                    b.f[j1]-=2;
                    dfs(len-5,b,sum+1);
                    b=x;
                }
           }
    int w=0;
    //cout<<"dan"<<" ";
    for(int i=0;i<=13;i++)
    if(x.f[i]>0)
    {//cout<<i<<" ";
        b.f[i]=0;
        w++;
    }
//  cout<<endl<<w<<" "<<sum<<endl;
    dfs(0,b,sum+w);
    b=x;
}
int yjn()
{
    //freopen("landlords.in","r",stdin);
    //freopen("landlords.out","w",stdout);
    scanf("%d%d",&t,&n);
    while(t--)
    {
        ans=1000000;
        memset(a.f,0,sizeof(a.f));
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            if(x==0)a.f[13]++;
            else
            {
                if(x==1)a.f[12]++;
                else a.f[x-2]++;
            }
            scanf("%d",&x);
        }
        dfs(n,a,0);
        printf("%d
",ans);
    }
}
int qty=yjn();
int main(){;}