P2540 斗地主增强版

思路：顺子暴力搜，剩下的牌我不会贪心所以用记忆化搜索(或者dp)；
注意：双王不能当对，二不算顺子
代码
  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cctype>
  5 #include <algorithm>
  6 using namespace std;
  7 
  8 #define res register int
  9 #define inf 0x3f3f3f3f
 10 inline int read() {
 11     int x(0),f(1); char ch;
 12     while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
 13     while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
 14     return x*f;
 15 }
 16 
 17 int n,T,ans;
 18 int a[20];
 19 int f[25][25][25][25];
 20 //单个牌的数目，双，三，四，王
 21 int c[5];
 22 
 23 template <typename T>
 24 inline T my_max(T a,T b) {return a<b?a:b;}
 25 template <typename T>
 26 inline T my_min(T a,T b) {return a<b?a:b;}
 27 
 28 int calc(int a,int b,int c,int d)
 29 {
 30     if(a<0 || b<0 || c<0 || d<0) return inf;
 31     if(!c && !d)    return a+b;
 32     if(~f[a][b][c][d]) return f[a][b][c][d];
 33     //拆四
 34     int tmp=my_min(calc(a+1,b,c+1,d-1),calc(a+2,b+2,c,d-1));
 35     //拆三
 36     tmp=my_min(tmp,my_min(calc(a+1,b+1,c-1,d),calc(a+3,b,c-1,d)));
 37     //四带一
 38     tmp=my_min(tmp,my_min(calc(a-2,b,c,d-1),calc(a,b-1,c,d-1))+1);
 39     //四带二
 40     tmp=my_min(tmp,my_min(calc(a,b-2,c,d-1),calc(a,b,c,d-2))+1);
 41     //三带一
 42     tmp=my_min(tmp,my_min(calc(a-1,b,c-1,d),calc(a,b-1,c-1,d))+1);
 43     return f[a][b][c][d]=tmp;
 44 }
 45 void dfs(int x)
 46 {
 47     if(x>=ans) return ;
 48     bool f=true;
 49     int cnt;
 50     //暴力出顺子
 51     for(res k=1 ; k<=3 ; k++)
 52         for(res i=3 ; i<=14 ; i++)
 53         {
 54             f=true; 
 55             if(k==1)      cnt=5; 
 56             else if(k==2) cnt=3;
 57             else          cnt=2;
 58             while(f&&i+cnt-1<=14)
 59             {
 60                 for(res j=1 ; j<=cnt ; j++)
 61                     if(a[i+j-1]<k) {
 62                         f=false; break;
 63                     }
 64                 if(!f)  continue;
 65                 for(res j=1 ; j<=cnt ; j++)
 66                     a[i+j-1]-=k;
 67                 dfs(x+1);
 68                 for(res j=1 ; j<=cnt ; j++)
 69                     a[i+j-1]+=k;
 70                 cnt++;//看有没有更长的顺子
 71             }
 72         }
 73     c[1]=c[2]=c[3]=c[4]=0;
 74     for(res i=3 ; i<=15 ; i++) c[a[i]]++;
 75     if(a[0]==2) ans=my_min(ans,x+calc(c[1],c[2],c[3],c[4])+1);
 76     //王炸
 77     ans=my_min(ans,x+calc(a[0]+c[1],c[2],c[3],c[4]));
 78 }
 79 
 80 int main()
 81 {
 82     T=read(); n=read();
 83     memset(f,-1,sizeof(f));
 84     while(T--)
 85     {
 86         memset(a,0,sizeof(a));
 87         ans=n;
 88         for(res i=1 ; i<=n ; i++)
 89         {
 90             int x=read(),y=read();
 91             if(x==0)      a[0]++;
 92             else if(x>=3) a[x]++;
 93             else if(x==1) a[14]++;
 94             else if(x==2) a[15]++;
 95         }
 96         dfs(0);
 97         printf("%d
",ans);
 98     }
 99 
100     return 0;
101 }
View Code