[BZOJ 4325]斗地主

danihao123 posted @ 2016年8月03日 14:18 in 题解 with tags DFS NOIP bzoj , 195 阅读
转载请注明出处:http://danihao123.is-programmer.com/

是的你没有看错!就是这道坑提!

这题基本是个半成品,歧义真的,真的,真的很大。

至于方法?我们注意到同样的牌能一起出就尽可能避免拆开。例如,四带二分成炸弹加两单点(对子)肯定不好。三带一或者三带二也如此。先考虑不出顺子的最优解,并据此进行深度限制,再考虑出顺子。

然后,DFS暴搜即可。

顺便讲一下坑点:

  1. 顺子可以有A。
  2. 三带一,三带二,四代二都可以有头。但是大小头要区别开。

代码:

/**************************************************************
    Problem: 4325
    User: danihao123
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans;
int cnt[5],hand[15];
void dfs(int x){
    if(x>ans)
        return;
    int i,j,rest=0;
    memset(cnt,0,sizeof(cnt));
    for(i=0;i<=14;i++){
        cnt[hand[i]]++;
    }
    while(cnt[4]>0){
        cnt[4]--;
        rest++;
        if(cnt[2]>=2)
            cnt[2]-=2;
        else
            if(cnt[1]>=2)
                cnt[1]-=2;
    }
    while(cnt[3]>0){
        cnt[3]--;
        rest++;
        if(cnt[2]>0)
            cnt[2]--;
        else
            if(cnt[1]>0)
                cnt[1]--;
    }
    if(hand[0] && hand[1] && cnt[1]>=2)
        rest--;
    ans=min(ans,cnt[1]+cnt[2]+rest+x);
    for(i=3;i<=10;i++){
        for(j=i;j<=14 && hand[j];j++){
            hand[j]--;
            if(j-i+1>=5)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]++;
    }
    for(i=3;i<=12;i++){
        for(j=i;j<=14 && hand[j]>=2;j++){
            hand[j]-=2;
            if(j-i+1>=3)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=2;
    }
    for(i=3;i<=13;i++){
        for(j=i;j<=14 && hand[j]>=3;j++){
            hand[j]-=3;
            if(j-i+1>=2)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=3;
    }
}
int main(){
    int T,u,v;
    register int i;
    scanf("%d%d",&T,&n);
    while(T--){
        ans=n;
        memset(hand,0,sizeof(hand));
        for(i=1;i<=n;i++){
            scanf("%d%d",&u,&v);
            if(!u){
                if(v==2)
                    hand[1]++;
                else
                    hand[0]++;
            }else{
                if(u==1)
                    hand[14]++;
                else
                    hand[u]++;
            }
        }
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter