【Noip2015】斗地主

题目

#include<bits/stdc++.h>

using namespace std;

int pai[20],T;

//pai[]统计牌的数量

int n;

int ans;

void shunzi(int step);//顺子

void feiji(int step);//飞机

void liandui(int step);//连对

int sanpai();

void chupai(int step){

    if (step>=ans)

        return;

    ans=min(ans,step+sanpai());

    feiji(step);

    shunzi(step);

    liandui(step);

}

void shunzi(int step){

    int l=0;

    for (int i=3;i<=13;i++){

        l=0;

        while (pai[i+l]>=1)

            l++;

        for (int j=l;j>=5;j--){

            for (int k=i;k<=i+j-1;k++)

                pai[k]=pai[k]-1;

            chupai(step+1);

            for (int k=i;k<=i+j-1;k++)

                pai[k]=pai[k]+1;

        }

    }

}

void feiji(int step){

    int l=0;

    for (int i=3;i<=13;i++){

        l=0;

        while (pai[i+l]>=3)

            l++;

        for (int j=l;j>=2;j--){

            for (int k=i;k<=i+j-1;k++)

                pai[k]=pai[k]-3;

            chupai(step+1);

            for (int k=i;k<=i+j-1;k++)

                pai[k]=pai[k]+3;

        }

    }

}

void liandui(int step){

    int l=0;

    for (int i=3;i<=13;i++){

        l=0;

        while (pai[i+l]>=2)

            l++;

        for (int j=l;j>=3;j--){

            for (int k=i;k<=i+j-1;k++)

                pai[k]=pai[k]-2;

            chupai(step+1);

            for (int k=i;k<=i+j-1;k++)

                pai[k]=pai[k]+2;

        }

    }

}

int sanpai(){

    bool wangzha=false;   // 可不可以王炸

    if (pai[1]==2)

        wangzha=true;

    int zhangshu[5];

    memset(zhangshu,0,sizeof(zhangshu));

    for (int i=2;i<=14;i++)

        zhangshu[pai[i]]++;

    zhangshu[1]+=pai[1];

    int num=0;

    if (zhangshu[2]==0&&zhangshu[3]==0&&zhangshu[4]==0&&wangzha==false)

        return zhangshu[1];

    if (zhangshu[2]==0&&zhangshu[3]==0&&zhangshu[4]==0&&wangzha)

        return zhangshu[1]-1;

	//以下1、2、3、4都代表出一种有1或2或3或4张的牌

    //炸->3+1  *  4+2  +  3+1     step 2

    while (!zhangshu[3]&&zhangshu[4]>=2&&zhangshu[1]==1&&zhangshu[2]==1){

        zhangshu[4]--;

        zhangshu[4]--;

        zhangshu[1]--;

        zhangshu[2]--;

        num=num+2;

    }

    //3->2+1   * 4+2 3+1 step 2

    while (!zhangshu[2]&&zhangshu[4]==1&&zhangshu[3]>=2&&zhangshu[1]==1){

        zhangshu[3]-=2;

        zhangshu[4]--;

        zhangshu[1]--;

        num+=2;

    }

    //3+4>2+1 3->2+1 * 4+2*2  1

    if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])

        while (zhangshu[4]&&zhangshu[3]&&zhangshu[2]){

            zhangshu[3]--;

            zhangshu[4]--;

            zhangshu[2]--;

            zhangshu[1]++;

            num++;

        }

    //

    if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])

        while (zhangshu[4]>=2&&zhangshu[3]>=2){

            zhangshu[3]-=2;

            zhangshu[4]-=2;

            num+=2;

        }

    //3+4>2+1  3->2+1 * 4+2*1 2

    if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])

        while (zhangshu[4]&&zhangshu[3]&&zhangshu[1]){

            zhangshu[1]--;

            zhangshu[3]--;

            zhangshu[4]--;

            zhangshu[2]++;

            num++;

        }

    //4+2*1

    while (zhangshu[4]&&zhangshu[1]>1){

        zhangshu[4]--;

        zhangshu[1]-=2;

        num++;

    }

    //4+2*2

    while (zhangshu[4]&&zhangshu[2]>1){

        zhangshu[4]--;

        zhangshu[2]-=2;

        num++;

    }

    //2->1+1 4+1+1

    while (zhangshu[4]&&zhangshu[2]){

        zhangshu[4]--;

        zhangshu[2]--;

        num++;

    }

    //3->1+2 *  3+1 3+2

    if (zhangshu[3]%3==0&&zhangshu[1]+zhangshu[2]<=1)

        while (zhangshu[3]>=3){

            zhangshu[3]-=3;

            num+=2;

        }

    //3+1

    while (zhangshu[3]&&zhangshu[1]){

        zhangshu[3]--;

        zhangshu[1]--;

        num++;

    }

    //3+2

    while (zhangshu[3]&&zhangshu[2]){

        zhangshu[3]--;

        zhangshu[2]--;

        num++;

    }

    //4->2 + 1*2   3+2 4+1*2

    while (zhangshu[4]>1&&zhangshu[3]){

        zhangshu[4]-=2;

        zhangshu[3]--;

        num+=2;

    }

    //4->2*2  3+2 3+2

    while (zhangshu[4]&&zhangshu[3]>1){

        zhangshu[4]--;

        zhangshu[3]-=2;

        num+=2;

    }

    //3->1+2  *  3+1  3+2

    while (zhangshu[3]>2){

        zhangshu[3]-=3;

        num+=2;

    }

    //4->2+2 * 4+2*2

    while (zhangshu[4]>1){

        zhangshu[4]-=2;

        num+=1;

    }

    if (wangzha==true&&zhangshu[1]>=2)

        return num+zhangshu[1]+zhangshu[2]+zhangshu[3]+zhangshu[4]-1;

    else

        return num+zhangshu[1]+zhangshu[2]+zhangshu[3]+zhangshu[4];

}

int main(){

    scanf("%d%d",&T,&n);

    while (T--){

        ans=n;

        memset(pai,0,sizeof(pai));

        for (int i=1;i<=n;i++){

            int x,y;

            scanf("%d%d",&x,&y);

            if (x==1){

                pai[14]++;

            }

            else if (x==0)

                pai[1]++;

            else

                pai[x]++;

        }

        chupai(0);//出牌

        printf("%d\n",ans);

		return 0;

    }

    return 0;

}

//此方法参照luogu题解