LOJ2422 NOIP2015 斗地主 【搜索+贪心】*

时间：2023-03-10 05:26:58
LOJ2422 NOIP2015 斗地主 【搜索+贪心】*

LOJ2422 NOIP2015 斗地主

LINK

题目大意很简单，就是问你斗地主的一分手牌最少多少次出完

然后我们发现对于一种手牌状态，不考虑顺子的情况是可以贪心做掉的

然后我们直接枚举一下顺子出牌情况就可以了

LOJ上的数据随便写点基本贪心就行了

如果想过UOJ上的加强版的话还是把中间那一部分毒瘤的特判更优情况加上吧

当然也有个Smallfat大神用DP做掉的

我感觉DP更严谨一些，但是毕竟贪心好写嘛

 #include<bits/stdc++.h>

 using namespace std;

 #define N 20

 int n,ans,is;

 int col[N],cnt[N],tmp[N];

 int cal(){

   for(int i=;i<=;i++)tmp[i]=cnt[i];

   int res=;

   while(tmp[]&&tmp[]>=)res++,tmp[]--,tmp[]-=;

   while(tmp[]&&tmp[]>=)res++,tmp[]--,tmp[]-=;

   //

   while(tmp[]&&!tmp[]&&tmp[]>=&&tmp[])    res+=,tmp[]--,tmp[]-=,tmp[]--;

   while(!tmp[]&&tmp[]&&tmp[]>=&&!tmp[])   res+=,tmp[]--,tmp[]-=;

   while(tmp[]&&tmp[]&&tmp[]&&tmp[]>=)     res+=,tmp[]--,tmp[]--,tmp[]--,tmp[]-=;

   while(tmp[]&&tmp[]&&!tmp[]&&tmp[]>=)    res+=,tmp[]--,tmp[]--,tmp[]-=;

   while(!tmp[]&&!tmp[]&&tmp[]>=&&tmp[]>=)res+=,tmp[]-=,tmp[]-=;

   while(!tmp[]&&!tmp[]&&tmp[]>=&&tmp[])   res+=,tmp[]-=,tmp[]--;

   //

   while(tmp[]&&tmp[])res++,tmp[]--,tmp[]--;

   while(tmp[]>=)res++,tmp[]-=;

   while(tmp[]&&tmp[])res++,tmp[]--,tmp[]--;

   while(tmp[]&&tmp[])res++,tmp[]--,tmp[]--;

   if(is&&tmp[]>=)tmp[]-=,res++;

   return res+tmp[]+tmp[]+tmp[]+tmp[];

 }

 bool check(int l,int r,int num){

   for(int i=l;i<=r;i++)if(col[i]<num)return ;

   return ;

 }

 void modify(int l,int r,int num){

   for(int i=l;i<=r;i++){

     cnt[col[i]]--;

     col[i]+=num;

     cnt[col[i]]++;

   }

 }

 void dfs(int step){

   if(step>=ans)return;

   ans=min(ans,step+cal());

   for(int l=;l<=;l++){

     for(int len=;len+l-<=;len++){

       int r=len+l-;

       if(!check(l,r,))break;

       modify(l,r,-);

       dfs(step+);

       modify(l,r,);

     }

   }

   for(int l=;l<=;l++){

     for(int len=;len+l-<=;len++){

       int r=len+l-;

       if(!check(l,r,))break;

       modify(l,r,-);

       dfs(step+);

       modify(l,r,);

     }

   }

   for(int l=;l<=;l++){

     for(int len=;len+l-<=;len++){

       int r=len+l-;

       if(!check(l,r,))break;

       modify(l,r,-);

       dfs(step+);

       modify(l,r,);

     }

   }

 }

 void solve(){

   int op,x;ans=n;

   for(int i=;i<=;i++)col[i]=,cnt[i]=;

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

     scanf("%d%d",&op,&x);

     if(op>)op--;

     else if(op)op=;

     col[op]++;

   }

   for(int i=;i<=;i++)if(col[i])cnt[col[i]]++;

   cnt[]+=col[];

   is=(col[]==);

   dfs();

   printf("%d\n",ans);

 }

 int main(){

   int T;scanf("%d%d",&T,&n);

   while(T--)solve();

   return ;

 }