[补档][NOIP2015] 斗地主

[NOIP2015] 斗地主

题目

传送门：http://cogs.pro/cogs/problem/problem.php?pid=2106

INPUT

第一行包含用空格隔开的2个正整数Tn，表示手牌的组数以及每组手牌的张数。

接下来T组数据，每组数据n行，每行一个非负整数对aibi表示一张牌，其中ai示牌的数码，bi表示牌的花色，中间用空格隔开。特别的，我们用1来表示数码A，11表示数码J，12表示数码Q，13表示数码K；黑桃、红心、梅花、方片分别用1-4来表示；小王的表示方法为01，大王的表示方法为02。

OUTPUT

共T行，每行一个整数，表示打光第i手牌的最少次数。

SAMPLE

INPUT1

1 8

7 4

8 4

9 1

10 4

11 1

5 1

1 4

1 1

OUTPUT1

INPUT2

1 17

12 3

4 3

2 3

5 4

10 2

3 3

12 2

0 1

1 3

10 1

6 2

12 1

11 3

5 2

12 4

2 2

7 2

OUTPUT2

解题报告

考试时光顾着T3了，看到它时间根本不够= =，拿了小数据特判分走人= =

显然是个暴搜模拟。

首先，显然花色没用，大王小王也可以看做一样的牌，而且，出牌顺序显然没有影响。

那么剩下的就很简单了，我们先出牌多的（正确性显然，因为这样答案一开始就不会很大，然后你可以用当前答案剪枝，因为已经不比当前答案优的解不可能推出最优解，这样，你可以利用较优的解减掉许多劣解，从而优化），并且，显然顺子一般来说要比带牌要优，那么剩下的就很简单了，注意一些出牌规则，不要像某些不会斗地主的小兄弟（hww：喵喵喵？）一样= =

要注意的是，顺子不一定越长越好，比如考虑这样一副牌：

3 4 5 6 7 8 9 9 10 10 J J

若是以越长越优的话，你会做出先打出顺子3~J，再单打9、10、J的决定，但显然打3~8的顺子加9~J的连对更优一些，所以我们在枚举顺子时，需要枚举所有可能的长度。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 using namespace std;
  5 inline int read(){
  6     int sum(0);
  7     char ch(getchar());
  8     for(;ch<'0'||ch>'9';ch=getchar());
  9     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
 10     return sum;
 11 }
 12 int size[30];
 13 int n,ans;
 14 inline int get_val(int x){
 15     if(x==1)
 16         return 12;
 17     if(x==2)
 18         return 13;
 19     if(x==0)
 20         return 14;
 21     return x-2;
 22 }
 23 inline int doit(){
 24     int tmp(0);
 25     int tp[6]={0};
 26     for(int i=1;i<=14;i++)
 27         tp[size[i]]++;
 28     while(tp[4]&&tp[2]>=2)
 29         tmp++,tp[4]--,tp[2]-=2;//四带俩对
 30     while(tp[4]&&tp[1]>=2)
 31         tmp++,tp[4]--,tp[1]-=2;//四带俩单
 32     while(tp[3]&&tp[2]>=1)
 33         tmp++,tp[3]--,tp[2]--;//三带二
 34     while(tp[3]&&tp[1]>=1)
 35         tmp++,tp[3]--,tp[1]--;//三带一
 36     tmp+=tp[1]+tp[2]+tp[3]+tp[4];
 37     return tmp;
 38 }
 39 inline int my_min(int a,int b){
 40     return a<b?a:b;
 41 }
 42 inline void dfs(int cnt){
 43     if(cnt>ans)
 44         return;
 45     int x(doit());
 46     ans=my_min(ans,cnt+x);
 47     for(int i=1;i<=11;i++){//三顺子
 48         int j;
 49         for(j=i;size[j]>=3&&j<=12;j++);
 50         if(j-i<2)
 51             continue;
 52         for(int k=j;k-i>=2;k--){
 53             for(int l=i;l<k;l++)
 54                 size[l]-=3;
 55             dfs(cnt+1);
 56             for(int l=i;l<k;l++)
 57                 size[l]+=3;
 58         }
 59     }
 60     for(int i=1;i<=10;i++){//连对
 61         int j;
 62         for(j=i;size[j]>=2&&j<=12;j++);
 63         if(j-i<3)
 64             continue;
 65         for(int k=j;k-i>=3;k--){
 66             for(int l=i;l<k;l++)
 67                 size[l]-=2;
 68             dfs(cnt+1);
 69             for(int l=i;l<k;l++)
 70                 size[l]+=2;
 71         }
 72     }
 73     for(int i=1;i<=8;i++){//顺子
 74         int j;
 75         for(j=i;size[j]>=1&&j<=12;j++);
 76         if(j-i<5)
 77             continue;
 78         for(int k=j;k-i>=5;k--){
 79             for(int l=i;l<k;l++)
 80                 size[l]--;
 81             dfs(cnt+1);
 82             for(int l=i;l<k;l++)
 83                 size[l]++;
 84         }
 85     }
 86 }
 87 inline int gg(){
 88 //  freopen("landlords.in","r",stdin);
 89 //  freopen("landlords.out","w",stdout);
 90     int T(read());
 91     n=read();
 92     while(T--){
 93         memset(size,0,sizeof(size));
 94         for(int i=1;i<=n;i++){
 95             int x(read()),y(read());
 96             size[get_val(x)]++;
 97         }
 98         ans=doit();
 99         dfs(0);
100         printf("%d
",ans);
101     }
102     return 0;
103 }
104 int K(gg());
105 int main(){;}

View Code

这一顿暴搜= =