题目描述

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A 到K 加上大小王的共54 张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 n 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。

现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

 

输入描述:

输入第一行包含用空格隔开的 2 个正整数 T, n ，表示手牌的组数以及每组手牌的张数。
接下来 T 组数据，每组数据 n 行，每行一个非负整数对ai,bi，表示一张牌，其中ai表示牌的数码，bi表示牌的花色，中间用空格隔开。特别的，我们用 1 来表示数码 A，11 表示数码 J，12 表示数码 Q，13 表示数码 K；黑桃、红心、梅花、方片分别用 1-4 来表示；小王的表示方法为 0 1，大王的表示方法为 0 2。

输出描述:

输出共 T 行，每行一个整数，表示打光第 i 组手牌的最少次数。

示例1

输入
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
输出
3
说明
共有1 组手牌，包含8 张牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A 以及黑桃A。可以通过打单顺子（方片7，方片8，黑桃9，方片10，黑桃J），单张牌（黑桃5）以及对子牌（黑桃A 以及方片A）在3 次内打光。

备注

对于不同的测试点，我们约定手牌组数T与张数n的规模如下:

所有手牌都是随机生成的

解答

  • NOIP 2015 斗地主的增强版。不仅仅是数据增强了，其实规则也稍有变化，在这

    道题里要注意大小王不再算是一对了，不能当做对子用。

  • 如果打过牌，可能会想到一些贪心的做法，但是我相信肯定有人见到这道题之前

    完全不会打牌（比如我），所以预处理就只好用dp了。

  • 设 dp[i][j][k][z][l]dp[i][j][k][z][l] 表示出现过一次的数码有 ii 个，出现过两次的数码有 jj 个，出现过三次的数码有 kk 个，出现过四次的数码有 zz 个,王有 ll 个的最小出牌次数。

  • 如果只是按照题目所给的方法进行转移并不能AC，因为还有一种出牌方法叫做

    拆牌，所以出现了以下两种新的转移：

注意循环的次序，一定要保证等式右边的比左边的先循环到。
代码： 
# include <cstdio>
# include <iostream>
# include <cstring>
# define R register int

using namespace std;

int T,n,ans;
int a[16];
int dp[25][25][25][25][3];
int num,col,coun[5];
bool id;

void dfs (int x)
{
    if(x>=ans) return;    
    bool f;
    int cnt;
    for (R k=1;k<=3;++k)
        for (R i=1;i<=12;++i)
        {
            f=true;
            if(k==1) cnt=5;
            if(k==2) cnt=3;
            if(k==3) cnt=2;
            while (f&&i+cnt-1<=12)
            {
                for (R j=1;j<=cnt;++j)
                    if(a[i+j-1]<k) 
                    {
                        f=false;
                        break;
                    }
                if(f==false) continue;
                for (R j=1;j<=cnt;++j)
                    a[i+j-1]-=k;
                dfs(x+1);
                for (R j=1;j<=cnt;++j)
                    a[i+j-1]+=k;
                cnt++;
            }
        }
    coun[1]=coun[2]=coun[3]=coun[4]=coun[5]=0;
    for (int i=1;i<=13;++i)
        coun[ a[i] ]++;
    coun[5]=a[14];
    ans=min(ans,x+dp[ coun[1] ][ coun[2] ][ coun[3] ][ coun[4] ][ coun[5] ]);
}

void init ()
{
    int x=100;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0][0][0][0]=0;

    for (int z=0;z<=n;++z)
        for (int k=0;k<=n;++k)
            for (int i=0;i<=n;++i)
                for (int j=0;j<=n;++j)        
                    for (int l=0;l<=2;++l)
                    {
                        x=100;
                        if(i>0) x=min(x,dp[i-1][j][k][z][l]+1);
                        if(j>0) x=min(x,dp[i][j-1][k][z][l]+1);
                        if(k>0) x=min(x,dp[i][j][k-1][z][l]+1);
                        if(z>0) x=min(x,dp[i][j][k][z-1][l]+1);
                        if(l>0) x=min(x,dp[i][j][k][z][l-1]+1);
                        if(l>1) x=min(x,dp[i][j][k][z][l-2]+1);
                        //单权值
                        if(i>0&&k>0) x=min(x,dp[i-1][j][k-1][z][l]+1);
                        if(l>0&&k>0) x=min(x,dp[i][j][k-1][z][l-1]+1); 
                        //三带一 
                        if(j>0&&k>0) x=min(x,dp[i][j-1][k-1][z][l]+1);
                        //三带二                        

                        if(i>1&&z>0) x=min(x,dp[i-2][j][k][z-1][l]+1);
                        if(i>0&&z>0&&l>0) x=min(x,dp[i-1][j][k][z-1][l-1]+1);
                        if(z>0&&l>1) x=min(x,dp[i][j][k][z-1][l-2]+1);
                        if(j>0&&z>0) x=min(x,dp[i][j-1][k][z-1][l]+1);
                        if(j>1&&z>0) x=min(x,dp[i][j-2][k][z-1][l]+1);
                        if(z>1) x=min(x,dp[i][j][k][z-2][l]+1);
                        //四带二
                        if(z>0) x=min(x,dp[i+1][j][k+1][z-1][l]);
                        if(k>0) x=min(x,dp[i+1][j+1][k-1][z][l]);
                        dp[i][j][k][z][l]=min(dp[i][j][k][z][l],x);
                    }
}

int main()
{
    scanf("%d%d",&T,&n);
    init();
    while (T--)
    {
        memset(a,0,sizeof(a));
        ans=n;
        for (int i=1;i<=n;++i)
        {
            scanf("%d%d",&num,&col);
            if(num==0)
            {
                a[14]++;
                continue;
            }
            if(num>=3) a[num-2]++;
            if(num==1) a[12]++;
            if(num==2) a[13]++;
        }
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}


来源：shzr