P2668 [NOIP2015 提高组] 斗地主

· · 个人记录

本文同步发表于我的博客园

没看到有人对贪心进行分析，并且第一篇题解哪怕是修改后还是错的，所以就试着推了一下然后写了这篇题解。

暴力搜顺子，DP（贪心）出散牌就不说了。

首先 4+2(1) 肯定比 4+2(2) 优先，因为 2 可以拆成 2(1)。

但实际上尴尬的情况只有 \bm{\{4,1\}} 必须出两次，而拆的话并没有改变 1 的奇偶性，还不如不拆。所以两者谁优先都无所谓。

并且我们可以发现这两种最先出肯定没问题。因为拆 3 肯定比拆 4 来得好，拆 4 只是在没有 3 的时候才会做出的事情，因为 4 能多带。除非出现上面那种尴尬的情况，但那种情况是 1,2 不够了，并不妨碍我们先出这两种。

出完后剩下如果还剩 4，那么 1,2 最多都只有一张，这时候拆 3 继续出上面两种是最优的。除非出现上面那种尴尬的情况或者 4 不够用了，容易发现两种情况分别为偶数个 4 加上一个或零个 2 加上 3 和 \{4,3,2,1\}。

特判完这两种情况后就没有 4 或者 3 了。

对于没有 4 的情况，优先出 3+2 和 3+1，出完后如果剩下至少两个 3 就拆；对于没有 3 的情况，如果还有一个 1 那么必然拆 4 为 3,1，因为消掉这个 1 一定不劣，然后如果 4 还有至少两个就可以拆 4 为 2,2。

#include<bits/stdc++.h>
using namespace std;
#define Min(x,y)((x)<(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
int num[16],h[5],mn;
void chupai(int step);
void shunzi(int step)
{
    int i,j,k;
//  cerr<<"shunzi0\n";
    For(i,3,10)
    {
        j=i;
        while(num[j])j++;
        j--;
        while(j>i+3)
        {
            For(k,i,j)num[k]--;
            chupai(step+1);
            For(k,i,j)num[k]++;
            j--;
        }
    }
//  cerr<<"shunzi1\n";
}
void liandui(int step)
{
    int i,j,k;
//  cerr<<"liandui0\n";
    For(i,3,12)
    {
        j=i;
        while(num[j]>1)j++;
        j--;
        while(j>i+1)
        {
            For(k,i,j)num[k]-=2;
            chupai(step+1);
            For(k,i,j)num[k]+=2;
            j--;
        }
    }
//  cerr<<"liandui1\n";
}
void feiji(int step)
{
    int i,j,k;
//  cerr<<"feiji0\n";
    For(i,3,13)
    {
        j=i;
        while(num[j]>2)j++;
        j--;
        while(j>i)
        {
            For(k,i,j)num[k]-=3;
            chupai(step+1);
            For(k,i,j)num[k]+=3;
            j--;
        }
    }
//  cerr<<"feiji1\n";
}
int sanpai()
{
    int i,ret=0;
//  cerr<<"sanpai0\n";
    h[1]=num[1];
    For(i,2,4)h[i]=0;
    For(i,2,14)h[num[i]]++;
    while(h[4]&&h[1]>1)h[4]--,h[1]-=2,ret++;
    //4+2(1)
    while(h[4]&&h[2]>1)h[4]--,h[2]-=2,ret++;
    //4+2(2)
    while(h[4]&&h[3])
    {
        if(!(h[4]&1)&&h[3]==1||h[4]==1&&h[3]==1&&h[2]&&h[1])break;
        h[3]--,h[2]++,h[1]++;
        while(h[4]&&h[2]>1)h[4]--,h[2]-=2,ret++;
        while(h[4]&&h[1]>1)h[4]--,h[1]-=2,ret++;
    }
    //3->2,1 with 4
    if(h[4]&&!(h[4]&1)&&h[3]==1)
    {
        h[4]--,h[2]++,h[1]=h[3]=0,ret++;
        if(h[2]>1)h[2]-=2,h[4]--,ret++;
    }
    if(h[4]==1&&h[3]==1&&h[2]&&h[1])return ret+2;
    //special cases
    while(h[3]&&h[1])h[3]--,h[1]--,ret++;
    //3+1
    while(h[3]&&h[2])h[3]--,h[2]--,ret++;
    //3+2
    while(h[3]>1)
    {
        h[3]--,h[2]++,h[1]++;
        while(h[3]&&h[1])h[3]--,h[1]--,ret++;
        while(h[3]&&h[2])h[4]--,h[2]--,ret++;
    }
    //3->2,1 with 3
    if(h[4]&&h[1])
    {
        h[4]--,h[1]=2,h[3]++;
        if(h[2])h[3]=0,h[2]--,ret++;
        else h[3]=0,h[1]--,ret++;
        if(h[4])h[4]--,h[1]=0,ret++;
    }
    //4->3,1
    if(h[4]&&h[2])h[4]--,h[2]=0,ret++;
    //2->1,1 with 4
    while(h[4]>1)h[4]-=2,ret++;
    //4->2,2 with 4
//  cerr<<"sanpai1\n";
    return ret+h[1]+h[2]+h[3]+h[4]-(num[1]==2&&h[1]>1);
}
void chupai(int step)
{
    if(step>=mn)return;
//  cerr<<"chupai0\n";
    int tmp=sanpai();
//  cerr<<"chupai1\n";
    mn=Min(mn,tmp+step);
    shunzi(step);
    liandui(step);
    feiji(step);
}
int main()
{
    int T,i,a,b,n;
    cin>>T>>n;
    while(T--)
    {
        mn=n;
        For(i,1,14)num[i]=0;
        For(i,1,n)cin>>a>>b,num[(!a?1:(a==1?14:a))]++;
        chupai(0);
        cout<<mn<<endl;
    }
    return 0;
}