[补档][NOIP2015] 斗地主

时间：2023-03-09 21:19:25
[补档][NOIP2015] 斗地主

[NOIP2015] 斗地主

题目

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

3

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

6

解题报告

考试时光顾着T3了，看到它时间根本不够= =，拿了小数据特判分走人= =
显然是个暴搜模拟。
首先，显然花色没用，大王小王也可以看做一样的牌，而且，出牌顺序显然没有影响。
那么剩下的就很简单了，我们先出牌多的（正确性显然，因为这样答案一开始就不会很大，然后你可以用当前答案剪枝，因为已经不比当前答案优的解不可能推出最优解，这样，你可以利用较优的解减掉许多劣解，从而优化），并且，显然顺子一般来说要比带牌要优，那么剩下的就很简单了，注意一些出牌规则，不要像某些不会斗地主的小兄弟 （hww：喵喵喵？）一样= =
要注意的是，顺子不一定越长越好，比如考虑这样一副牌：
3 4 5 6 7 8 9 9 10 10 J J
若是以越长越优的话，你会做出先打出顺子3~J，再单打9、10、J的决定，但显然打3~8的顺子加9~J的连对更优一些，所以我们在枚举顺子时，需要枚举所有可能的长度。
 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 inline int read(){

     int sum();

     char ch(getchar());

     for(;ch<''||ch>'';ch=getchar());

     for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());

     return sum;

 }

 int size[];

 int n,ans;

 inline int get_val(int x){

     if(x==)

         return ;

     if(x==)

         return ;

     if(x==)

         return ;

     return x-;

 }

 inline int doit(){

     int tmp();

     int tp[]={};

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

         tp[size[i]]++;

     while(tp[]&&tp[]>=)

         tmp++,tp[]--,tp[]-=;//四带俩对

     while(tp[]&&tp[]>=)

         tmp++,tp[]--,tp[]-=;//四带俩单

     while(tp[]&&tp[]>=)

         tmp++,tp[]--,tp[]--;//三带二

     while(tp[]&&tp[]>=)

         tmp++,tp[]--,tp[]--;//三带一

     tmp+=tp[]+tp[]+tp[]+tp[];

     return tmp;

 }

 inline int my_min(int a,int b){

     return a<b?a:b;

 }

 inline void dfs(int cnt){

     if(cnt>ans)

         return;

     int x(doit());

     ans=my_min(ans,cnt+x);

     for(int i=;i<=;i++){//三顺子

         int j;

         for(j=i;size[j]>=&&j<=;j++);

         if(j-i<)

             continue;

         for(int k=j;k-i>=;k--){

             for(int l=i;l<k;l++)

                 size[l]-=;

             dfs(cnt+);

             for(int l=i;l<k;l++)

                 size[l]+=;

         }

     }

     for(int i=;i<=;i++){//连对

         int j;

         for(j=i;size[j]>=&&j<=;j++);

         if(j-i<)

             continue;

         for(int k=j;k-i>=;k--){

             for(int l=i;l<k;l++)

                 size[l]-=;

             dfs(cnt+);

             for(int l=i;l<k;l++)

                 size[l]+=;

         }

     }

     for(int i=;i<=;i++){//顺子

         int j;

         for(j=i;size[j]>=&&j<=;j++);

         if(j-i<)

             continue;

         for(int k=j;k-i>=;k--){

             for(int l=i;l<k;l++)

                 size[l]--;

             dfs(cnt+);

             for(int l=i;l<k;l++)

                 size[l]++;

         }

     }

 }

 inline int gg(){

 //  freopen("landlords.in","r",stdin);

 //  freopen("landlords.out","w",stdout);

     int T(read());

     n=read();

     while(T--){

         memset(size,,sizeof(size));

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

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

             size[get_val(x)]++;

         }

         ans=doit();

         dfs();

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

     }

     return ;

 }

 int K(gg());

 int main(){;}
这一顿暴搜= =

相关文章