时间戳

首页 > 技术文章 > Luogu 2540 斗地主增强版（搜索，动态规划）

Luogu 2540 斗地主增强版（搜索，动态规划）

SYCstudio 2017-10-05 11:40 原文

Luogu 2540 斗地主增强版（搜索，动态规划）

Description

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

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

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

具体规则如下：
此处输入图片的描述

Input

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

Output

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

Sample Input

1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

Sample Output

3

Http

Luogu:https://www.luogu.org/problem/show?pid=2540

Source

搜索，动态规划

解决思路

这是这一题的增强版。如果将原题的程序直接交到这里，只能获得76分。
为什么呢？因为我们没有考虑把三张的或四张的拆开来计算，比如下面这个例子

1 1 1 1 2 2 2 2

如果按照原来看作两个炸弹的观点，需要两步打出。但如果将其中一个炸弹拆成两对，将这8张牌看作4带2对的话，可以一步打出。
所以在上一题的基础上，我们在预处理的时候要加上几个条件。
但因为若按照原来按照\(F[i][j][k][l]\)表示单张\(i\)张，对子\(j\)组，三张的\(k\)组，四张的\(l\)组，并按照原来的循环顺序操作的话，会出现计算\(F[i][j][k][l]\)的时候需要\(F[i+1][……]\)的情况，所以考虑到4张可以拆成3张、2张、1张，3张可以拆成2张、1张，所以我们把\(i,j,k,l\)调换顺序，设\(F[i][j][k][l]\)表示炸弹\(l\)组，三张的\(k\)组，对子\(j\)组，单张\(i\)组，然后转移

一张
F[i][j][k][l]=min(F[i][j][k][l],F[i][j][k][l-1]+1);//打出一个单牌
两张
F[i][j][k][l]=min(F[i][j][k][l],F[i][j][k-1][l]+1);//打出一个对子
三张
F[i][j][k][l]=min(F[i][j][k][l],F[i][j-1][k][l]+1);//打出三张牌
F[i][j][k][l]=min(F[i][j][k][l],F[i][j-1][k][l-1]+1);//打出三带一
F[i][j][k][l]=min(F[i][j][k][l],F[i][j-1][k-1][l]+1);//打出三带二
F[i][j][k][l]=min(F[i][j][k][l],F[i][j-1][k+1][l+1]);//新增：三个拆成一对和一个
四张
F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j][k][l]+1);//打出四张牌
F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j][k][l-2]+1);//打出四带两张单牌
F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j][k-2][l]+1);//打出四带两对牌
F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j+1][k][l+1]);//新增：四个拆成三个和一个
F[i][j][k][l]=min(F[i][j][k][l],F[i-2][j][k][l]+1);//新增：两个四拆成一个四带两对
F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j][k-1][l]+1);//新增：四带一对

其他的地方与原题代码一致，请看这里

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxN=25;
const int Shunzi[4]={0,5,3,2};//i顺子至少需要多少张牌
const int inf=2147483647;

int n;
int Card[maxN];
int F[maxN][maxN][maxN][maxN];
int Ans;

void init();
void dfs(int step);
int now_step(int x1,int x2,int x3,int x4);

int main()
{
    int T;
    scanf("%d%d",&T,&n);
    init();
    while (T--)
    {
        memset(Card,0,sizeof(Card));
        Ans=n;
        for (int i=1;i<=n;i++)//输入
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if (a==0)//0是王
                Card[0]++;
            else
                if (a==1)
                    Card[14]++;
                else
                    Card[a]++;
        }
        dfs(0);
        printf("%d\n",Ans);
    }
    return 0;
}

void init()
{
    F[0][0][0][0]=0;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++)
            for (int k=0;k<=n;k++)
                for (int l=0;l<=n;l++)
                {
                    F[i][j][k][l]=i+j+k+l;
                    if (4*i+3*j+2*k+l<=n)
                    {
                        if (l!=0)//一张牌
                            F[i][j][k][l]=min(F[i][j][k][l],F[i][j][k][l-1]+1);//打出一个单牌
                        if (k!=0)//双牌
                            F[i][j][k][l]=min(F[i][j][k][l],F[i][j][k-1][l]+1);//打出一个对子
                        if (j!=0)//三张牌
                        {
                            F[i][j][k][l]=min(F[i][j][k][l],F[i][j-1][k][l]+1);//打出三张牌
                            if (l!=0)
                                F[i][j][k][l]=min(F[i][j][k][l],F[i][j-1][k][l-1]+1);//打出三带一
                            if (k!=0)
                                F[i][j][k][l]=min(F[i][j][k][l],F[i][j-1][k-1][l]+1);//打出三带二
                            if (j>=1)
                                F[i][j][k][l]=min(F[i][j][k][l],F[i][j-1][k+1][l+1]);//三个拆成一对和一个
                        }
                        if (i!=0)//四张牌
                        {
                            F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j][k][l]+1);//打出四张牌
                            if (l>=2)
                                F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j][k][l-2]+1);//打出四带两张单牌
                            if (k>=2)
                                F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j][k-2][l]+1);//打出四带两对牌
                            if (i>=1)
                                F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j+1][k][l+1]);//四个拆成三个和一个
                            if (i>=2)
                                F[i][j][k][l]=min(F[i][j][k][l],F[i-2][j][k][l]+1);//两个四拆成一个四带两对
                            if (k>=1)
                                F[i][j][k][l]=min(F[i][j][k][l],F[i-1][j][k-1][l]+1);//四带一对
                        }
                        //printf("(%d,%d,%d,%d) %d\n",i,j,k,l,F[i][j][k][l]);
                    }
                }
    return;
}

void dfs(int step)
{
    if (step>Ans)
        return;
    int Cnt[maxN];
    memset(Cnt,0,sizeof(Cnt));
    for (int i=2;i<=14;i++)//统计1张的、2张的、3张的和4张的分别有几组
        Cnt[Card[i]]++;
    Ans=min(Ans,step+now_step(Cnt[1],Cnt[2],Cnt[3],Cnt[4]));//统计当前剩下的都按照非顺子的方式打出去
    //cout<<Ans<<endl;
    for (int k=1;k<=3;k++)//枚举当前选择k顺子
    {
        for (int i=3;i<=14;i++)//枚举起始位置
        {
            int pos;
            for (pos=i;(pos<=14)&&(Card[pos]>=k);pos++)//枚举顺子结束位置
            {
                Card[pos]=Card[pos]-k;
                if (pos-i+1>=Shunzi[k])
                    dfs(step+1);
            }
            for (pos=pos-1;pos>=i;pos--)//将牌还原
                Card[pos]=Card[pos]+k;
        }
    }
    return;
}

int now_step(int x1,int x2,int x3,int x4)
{
    if (Card[0]==0)
        return F[x4][x3][x2][x1];//没有王
    if (Card[0]==1)
        return F[x4][x3][x2][x1+1];//只有一个王
    if (Card[0]==2)
        return min(F[x4][x3][x2][x1+2],F[x4][x3][x2][x1]+1);//将两张王看作两张单牌or一对牌
}

推荐阅读