NOIP2015 提高組 day1 T3 — 鬥地主

題解

模拟爆搜！！！

順子是關鍵！！！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,a[20],minn=26;
int r()
{
   int ret=0;
   for (int i=2; i<=16; i++)
   {
       if (a[i] == 4) ret++;
       if (a[i] == 3) ret++;
       if (a[i] == 2) ret++;
       if (a[i] == 1) ret++; 
   }
   return ret;
}
void dfs(int depth, int ans){
   if (ans > minn) return ;
   if (depth == n)
   {
       minn=ans;
       return ;
   }
   int tot=r();
   if (tot + ans < minn) minn=ans+tot; 
   for (int i=2; i<=16; i++){
       if (a[i] == 4) {
           for (int j=2; j<=15; j++) if (a[j] >= 2 && j!=i) 
               for (int k=j; k<=16; k++) if (a[k] >= 2 && k!=i && k!=j)
                   {
                       a[i]-=4; a[j]-=2; a[k]-=2;
                       dfs(depth+8,ans+1);
                       a[i]+=4; a[j]+=2; a[k]+=2;
                   } //四帶二對
           for (int j=2; j<=15; j++) if (a[j] >= 1 && j!=i)
               for (int k=j; k<=16; k++) if (a[k] >= 1 && k!=j && k!=i)
                   {
                       a[i]-=4; a[j]-=1; a[k]-=1;
                       dfs(depth+6,ans+1);
                       a[i]+=4; a[j]+=1; a[k]+=1; 
                   }//四帶二單 
       }
       if (a[i] >= 3){
           int cnt=1;
           for (int j=i+1; j<=14; j++)
               if (a[j] >= 3) cnt++; 
               else break;
               //到A就截止啦
           if (cnt >= 2){
               for (int j=i; j<=i+cnt-1; j++) a[j]-=3;
               dfs(depth+cnt*3,ans+1);
               for (int j=i; j<=i+cnt-1; j++) a[j]+=3;
           }
           for (int j=2; j<=16; j++) if (a[j] >= 2 && j!=i)
           {
               a[i]-=3; a[j]-=2;
               dfs(depth+5,ans+1);
               a[i]+=3; a[j]+=2; 
           }     
           for (int j=2; j<=16; j++) if (a[j] >= 1 && j!=i)
           {
               a[i]-=3; a[j]-=1;
               dfs(depth+4,ans+1);
               a[i]+=3; a[j]+=1;
           }
       }
       if (a[i] >= 2){ 
           if ( i!=2 ){  
               int cnt=1;
               for (int j=i+1; j<=14; j++)
                   if (a[j] >= 2) cnt++;
                   else break;
               if (cnt >= 3){
                   for (int j=i; j<=i+cnt-1; j++) a[j]-=2;
                   dfs(depth+cnt*2,ans+1);
                   for (int j=i; j<=i+cnt-1; j++) a[j]+=2;
               }
           }
       }
       if (a[i] >= 1){
           if ( i > 2 && i<11){
               int cnt=1;
               for (int j=i+1; j<=14; j++) 
                   if (a[j] >= 1) cnt++;
                   else break;
               if (cnt >= 5){
                   for (int j=i; j<=i+cnt-1; j++) a[j]-=1;
                   dfs(depth+cnt,ans+1);
                   for (int j=i; j<=i+cnt-1; j++) a[j]+=1;
               }
           }
           if (i == 15 && a[16] >= 1) {
               a[15]-=1; a[16]-=1;
               dfs(depth+2, ans+1);
               a[15]+=1; a[16]+=1;
           }       
       }
   }
}
int main(){
   scanf("%d%d",&T,&n);
   for (int j=1; j<=T; j++)
   {
       minn=26;
       memset(a,0,sizeof(a));
       for (int i=1; i<=n; i++)
       {
           int x,y;
           scanf("%d%d",&x,&y);
           if (x == 0 && y == 1) a[15]++;
           if (x == 0 && y == 2) a[16]++;
           if (x == 1) a[14]++;
           a[x]++;
       }
      dfs(0,0);
      printf("%d\n",minn);
   }
   return 0;
}