NOIP2015 斗地主增强版

题目:

   牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。
   现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
   需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
   具体规则如下:
  
   在此题中认为两个王不能组成对子牌。

思路:

   如果是原题那个随机数据,可以考虑直接强行广搜,但是增强版这样会T,所以考虑跳过这题优化。
   发现只有顺子会受到点数的限制(打出的牌要求点数连续),而其他的都没有(只要求不同)。所以考虑用dp来计算不打顺子的情况,设表示有个点数出现次数为需要的步数。每次也是按照规则转移,注意拆牌的情况。而打出顺子的情况还是搜索解决。

代码:

#include <bits/stdc++.h>
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
const int INF=2e9;
int calc(int x1,int x2,int x3,int x4){
#define nxt_calc calc(x[1],x[2],x[3],x[4])
    static int dp[20][20][20][20]={0},x[5];
    x[1]=x1;x[2]=x2;x[3]=x3;x[4]=x4;
    if(x1<0||x2<0||x3<0||x4<0)return INF;
    if(x1==0&&x2==0&&x3==0&&x4==0)return 0;
    int &now=dp[x1][x2][x3][x4];
    if(now)return now;
    now=INF;
    for(int i=4;i>=1;i--)
        for(int j=i-1;j>=0;j--){
            x[i]--;x[j]++;
            tomin(now,1+nxt_calc);
            x[i]++;x[j]--;
        }
    for(int i=1;i<=2;i++){
        for(int k=i;k<=4;k++)
            for(int p=3;p<=4;p++){
                x[k]--;x[k-i]++;x[p]--;x[p-3]++;
                tomin(now,1+nxt_calc);
                x[k]++;x[k-i]--;x[p]++;x[p-3]--;
            }
    }
    for(int i=1;i<=2;i++){
        for(int k=i;k<=4;k++)
            for(int p=k;p<=4;p++){
                 x[k]--;x[p]--;x[k-i]++;x[p-i]++;x[4]--;
                  tomin(now,1+nxt_calc);
                  x[k]++;x[p]++;x[k-i]--;x[p-i]--;x[4]++;
            }
        for(int k=i*2;k<=4;k++){
            x[k]--;x[k-i*2]++;x[4]--;
            tomin(now,1+nxt_calc);
            x[k]++;x[k-i*2]--;x[4]++;
        }
    }
    return now;
#undef nxt_calc
}
struct Landlords{
    int cnt[14];
    void read(int n){
        memset(cnt,0,sizeof cnt);
        for(int i=1,a,b;i<=n;i++){
            scanf("%d%d",&a,&b);
            if(a==0)cnt[a]++;
            else if(a==1)cnt[13]++;
            else cnt[a-1]++;
        }
    }
    int get(){
        int x[5]={0};
        for(int i=0;i<=13;i++)
            x[cnt[i]]++;
        if(cnt[0]==2)
            return min(calc(x[1]+2,x[2]-1,x[3],x[4]),calc(x[1],x[2]-1,x[3],x[4])+1);
        return calc(x[1],x[2],x[3],x[4]);
    }
};
int ans;
Landlords now;
const int SHUNZI_NED[]={5,3,2};
void dfs(int stp){
    if(stp>=ans)return;
    tomin(ans,stp+now.get());
    for(int q=1;q<=3;q++){
        int k=SHUNZI_NED[q-1];
        for(int i=2;i<=13;i++)
            for(int j=i+k-1;j<=13;j++){
                bool f=1;
                for(int p=i;p<=j&&f;p++)
                    if(now.cnt[p]<q)
                        f=0;
                if(f){
                    for(int p=i;p<=j;p++)
                        now.cnt[p]-=q;
                    dfs(stp+1);
                    for(int p=i;p<=j;p++)
                        now.cnt[p]+=q;
                }
            }
        }
}
int main(){
    int t,n;
    scanf("%d%d",&t,&n);
    while(t--){
        now.read(n);
        ans=INF;
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}