P2540 斗地主增强版

P2540斗地主增强版

参考大佬题解

思路：顺子暴力搜，剩下的牌我不会贪心所以用记忆化搜索(或者dp)；

注意：双王不能当对，二不算顺子

代码

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <cctype>

 #include <algorithm>

 using namespace std;

 #define res register int

 #define inf 0x3f3f3f3f

 inline int read() {

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

     while(!isdigit(ch=getchar())) if(ch=='-') f=-;

     while(isdigit(ch)) x=(x<<)+(x<<)+ch-'',ch=getchar();

     return x*f;

 }

 int n,T,ans;

 int a[];

 int f[][][][];

 //单个牌的数目，双，三，四，王

 int c[];

 template <typename T>

 inline T my_max(T a,T b) {return a<b?a:b;}

 template <typename T>

 inline T my_min(T a,T b) {return a<b?a:b;}

 int calc(int a,int b,int c,int d)

 {

     if(a< || b< || c< || d<) return inf;

     if(!c && !d)    return a+b;

     if(~f[a][b][c][d]) return f[a][b][c][d];

     //拆四

     int tmp=my_min(calc(a+,b,c+,d-),calc(a+,b+,c,d-));

     //拆三

     tmp=my_min(tmp,my_min(calc(a+,b+,c-,d),calc(a+,b,c-,d)));

     //四带一

     tmp=my_min(tmp,my_min(calc(a-,b,c,d-),calc(a,b-,c,d-))+);

     //四带二

     tmp=my_min(tmp,my_min(calc(a,b-,c,d-),calc(a,b,c,d-))+);

     //三带一

     tmp=my_min(tmp,my_min(calc(a-,b,c-,d),calc(a,b-,c-,d))+);

     return f[a][b][c][d]=tmp;

 }

 void dfs(int x)

 {

     if(x>=ans) return ;

     bool f=true;

     int cnt;

     //暴力出顺子

     for(res k= ; k<= ; k++)

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

         {

             f=true;

             if(k==)      cnt=;

             else if(k==) cnt=;

             else          cnt=;

             while(f&&i+cnt-<=)

             {

                 for(res j= ; j<=cnt ; j++)

                     if(a[i+j-]<k) {

                         f=false; break;

                     }

                 if(!f)  continue;

                 for(res j= ; j<=cnt ; j++)

                     a[i+j-]-=k;

                 dfs(x+);

                 for(res j= ; j<=cnt ; j++)

                     a[i+j-]+=k;

                 cnt++;//看有没有更长的顺子

             }

         }

     c[]=c[]=c[]=c[]=;

     for(res i= ; i<= ; i++) c[a[i]]++;

     if(a[]==) ans=my_min(ans,x+calc(c[],c[],c[],c[])+);

     //王炸

     ans=my_min(ans,x+calc(a[]+c[],c[],c[],c[]));

 }

 int main()

 {

     T=read(); n=read();

     memset(f,-,sizeof(f));

     while(T--)

     {

         memset(a,,sizeof(a));

         ans=n;

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

         {

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

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

             else if(x>=) a[x]++;

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

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

         }

         dfs();

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

     }

     return ;

 }