【NOIP2015】斗地主题解(DFS+贪心)

题目描述

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

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

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

本题数据随机，不支持hack，要hack或强力数据请点击这里

-----------------------------------------------------------------------------------------------------------------

搜索经典题目。

没什么别的思路，就是dfs+贪心

总体策略：先打顺子再打三带最后打单牌和对子

坑点巨多，调了好久才调出来……

#include<bits/stdc++.h>

using namespace std;

int T,n,sum[],ans,output[];

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){

        if (ch=='-') f=-;

        ch=getchar();

    }while(''<=ch&&ch<=''){

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

void dfs(int x)

{

    if (x>=ans) return;

    int k=;

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

    {

        if (sum[i]==) k=;

        else{

            k++;

            if (k>=){

                for (int j=i;j>=i-k+;j--) sum[j]--;

                dfs(x+);

                for (int j=i;j>=i-k+;j--) sum[j]++;

            }

        }

     }

     k=;

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

     {

         if (sum[i]<=) k=;

         else

         {

             k++;

             if (k>=)

             {

                 for (int j=i;j>=i-k+;j--) sum[j]-=;

                 dfs(x+);

                 for (int j=i;j>=i-k+;j--) sum[j]+=;

             }

         }

    }

    k=;

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

    {

        if (sum[i]<=) k=;

        else

        {

            k++;

            if (k>=)

            {

                for (int j=i;j>=i-k+;j--) sum[j]-=;

                dfs(x+);

                for (int j=i;j>=i-k+;j--) sum[j]+=;

            }

        }

    }

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

    {

        if (sum[i]<=)

        {

            if (sum[i]<=) continue;

            sum[i]-=;

            for (int j=;j<=;j++)

            {

                if (sum[j]<=||j==i) continue;

                sum[j]--;

                dfs(x+);

                sum[j]++;

            }

            for (int j=;j<=;j++)

            {

                if (sum[j]<=||j==i) continue;

                sum[j]-=;

                dfs(x+);

                sum[j]+=;

            }

            sum[i]+=;

        }

        else

        {

            sum[i]-=;

            for (int j=;j<=;j++)

            {

                if (sum[j]<=||j==i) continue;

                sum[j]--;

                dfs(x+);

                sum[j]++;

            }

            for (int j=;j<=;j++)

            {

                if (sum[j]<=||j==i) continue;

                sum[j]-=;

                dfs(x+);

                sum[j]+=;

            }

            sum[i]+=;

            sum[i]-=;

            for (int j=;j<=;j++)

            {

                if (sum[j]<=||j==i) continue;

                sum[j]--;

                for (int h=;h<=;h++)

                {

                    if (sum[h]<=||j==h) continue;

                    sum[h]--;

                    dfs(x+);

                    sum[h]++;

                }

                sum[j]++;

            }

            for (int j=;j<=;j++)

            {

                if (sum[j]<=||j==i) continue;

                sum[j]-=;

                for (int h=;h<=;h++)

                {

                    if (sum[h]<=||h==j) continue;

                    sum[h]-=;

                    dfs(x+);

                    sum[h]+=;

                }

                sum[j]+=;

            }

            sum[i]+=;

        }

    }

    for (int i=;i<=;i++) if (sum[i]) x++;

    ans=min(ans,x);

}

int main()

{

    T=read(),n=read();int ff=T;

    while(T--)

    {

        ans=0x7fffffff;

        int x,y;

        memset(sum,,sizeof(sum));

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

        {

            x=read(),y=read();

            if (x==) sum[]++;

            else if(x==) sum[]++;

            else sum[x]++;

        }

        dfs();

       cout<<ans<<endl;

    }

}

巴特西

【NOIP2015】斗地主题解(DFS+贪心)

题目描述

最新文章

热门文章

巴特西

【NOIP2015】斗地主 题解(DFS+贪心)

题目描述

最新文章

热门文章

【NOIP2015】斗地主题解(DFS+贪心)