P2668 斗地主
题目描述
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。
现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
具体规则如下：
本题数据随机，不支持hack，要hack或强力数据请点击这里
输入输出格式
输入格式：
第一行包含用空格隔开的2个正整数T和n，表示手牌的组数以及每组手牌的张数。
接下来T组数据，每组数据n行，每行一个非负整数对aibi表示一张牌，其中ai示牌的数码，bi表示牌的花色，中间用空格隔开。特别的，我们用1来表示数码A，11表示数码J，12表示数码Q，13表示数码K；黑桃、红心、梅花、方片分别用1-4来表示；小王的表示方法为01，大王的表示方法为02。
输出格式：
共T行，每行一个整数，表示打光第i手牌的最少次数。
输入输出样例
输入样例#1：
1 8 7 4 8 4 9 1 10 4 11 1 5 1 1 4 1 1
输出样例#1：
3
输入样例#2：
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
输出样例#2：
6
说明
样例1说明
共有1组手牌，包含8张牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A以及黑桃A。可以通过打单顺子（方片7，方片8，黑桃9，方片10，黑桃J），单张牌（黑桃5）以及对子牌（黑桃A以及方片A）在3次内打光。
对于不同的测试点， 我们约定手牌组数T与张数n的规模如下：
数据保证：所有的手牌都是随机生成的。
1 #include <cstdio> 2 #include <cctype> 3 #include <cstring> 4 #include <cstring> 5 6 const int MAXN=30; 7 const int INF=0x3f3f3f3f; 8 9 int T,n,ans; 10 11 int cardsum[MAXN],the_tim[MAXN]; 12 13 int shun[5]={0,5,3,2}; 14 15 inline void read(int&x) { 16 int f=1;register char c=getchar(); 17 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 18 for(;isdigit(c);x=x*10+c-48,c=getchar()); 19 x=x*f; 20 } 21 22 inline int min(int a,int b) {return a<b?a:b;} 23 24 inline void DFS(int now) { 25 if(now>ans) return; 26 memset(the_tim,0,sizeof the_tim); 27 for(int i=0;i<=14;++i) ++the_tim[cardsum[i]]; 28 int operation=0; 29 while(the_tim[4]) { 30 ++operation; 31 --the_tim[4]; 32 if(the_tim[2]>=2) the_tim[2]-=2; 33 else if(the_tim[1]>=2) the_tim[1]-=2; 34 } 35 while(the_tim[3]) { 36 ++operation; 37 --the_tim[3]; 38 if(the_tim[2]) --the_tim[2]; 39 else if(the_tim[1]) --the_tim[1]; 40 } 41 if(cardsum[0]&&cardsum[1]&&the_tim[1]>=2) --operation; 42 operation+=the_tim[1]+the_tim[2]; 43 ans=min(ans,operation+now); 44 for(int k=1;k<=3;++k) 45 for(int j,i=3;i<=14;++i) { 46 for(j=i;j<=14&&cardsum[j]>=k;++j) { 47 cardsum[j]-=k; 48 if(j-i+1>=shun[k]) DFS(now+1); 49 } 50 while(j>i) cardsum[--j]+=k; 51 } 52 return; 53 } 54 55 int hh() { 56 read(T);read(n); 57 while(T--) { 58 memset(cardsum,0,sizeof cardsum); 59 ans=INF; 60 for(int type,s,i=1;i<=n;++i) { 61 read(type);read(s); 62 if(!type) ++cardsum[--s]; 63 else if(type==1) ++cardsum[14]; 64 else ++cardsum[type]; 65 } 66 DFS(0); 67 printf("%d ",ans); 68 } 69 return 0; 70 } 71 72 int sb=hh(); 73 int main(int argc,char**argv) {;}