问题 B: NOIP2015 斗地主
时间限制: 3 Sec 内存限制: 1024 MB题目描述
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：
输入
第一行包含用空格隔开的2个正整数T,N，表示手牌的组数以及每组手牌的张数。
输出
共T行，每行一个整数，表示打光第T组手牌的最少次数。
样例输入
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
样例输出
3
提示
共有1组手牌，包含8张牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A以及黑桃A。可以通过打单顺子（方片7，方片8，黑桃9，方片10，黑桃J），单张
这道题为NOIP2015第一天第三题。属于爆搜类，没有任何算法，就是模拟加爆搜。由于有不同种打法，dfs分为好几层，本着先大后小便于剪枝的原则，先出顺子，再带牌，最后散着出。
首先，花色对结果无影响，其次大小王对结果是否有贡献只看是否出现其中之一，出现结果+1即可，未出现就不必管了（吐槽一下题目描述，没说四带二不算俩王，但测试点中确实不带）。还有一点值得注意的是大小顺序，首先是2不算顺子，其次1比3~13都大，因此可以把大小统一减2,1、2改为12、13便于使用。
先预处理出各个数字（以下都为预处理后的数字）的个数，开始分层爆搜。先提前说明各个数组，la[]为各个数字还剩几个没打，num[i]为数量为i的同数字牌还有几个
第一至三层为顺子，它们可以搜索到自己，因为一套牌可以出现多个顺子，至于顺子的长度，从大到小进行枚举，原理见上然后将搜索完的目标再次指向自己，在函数最后向下一层搜索。
第四，五层为带，四层为四带二，要注意是四带二不是四带一，因为这个卡了55%，带对带单都可以，又因为可以同时出四带两个单和四带两个双，因此需要引入一个bool型变量确认该次搜索由哪里传下来，若为上层则四带双和四带单都单独搜索，四带双继续指向本层，bool改变，只搜四带单，三同理。
第五层就是处理散牌了，不解释。
最后膜拜？大犇，有一个剪枝，若到盖层走的步数以比当前最优解大，则直接返回，貌似省了不少时间。
本来就是搜索题，只能说这些了，其实主要还是代码能力和脑洞。
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #include<algorithm> 7 #include<cmath> 8 using namespace std; 9 int t,n,ans=0x7fffffff; 10 int sum[14],la[14],num[5]; 11 void dfs6(int js){ 12 if(js>=ans)return; 13 int jj=0; 14 for(int i=4;i>=1;i--) 15 jj+=num[i]; 16 ans=min(ans,jj+js); 17 return; 18 } 19 void dfs5(int js,bool pd){ //3 _ 20 if(js>=ans)return; 21 int nn[5]; 22 memcpy(nn,num,sizeof(num)); 23 if(!pd) 24 { 25 for(int i=num[3];i>=1;i--) 26 { 27 if(num[2]>=i) 28 { 29 memcpy(num,nn,sizeof(num)); 30 num[3]-=i; 31 num[2]-=i; 32 dfs5(js+i,1); 33 memcpy(num,nn,sizeof(num));//记得还原，否则判断num[]将会失误。下同。 34 } 35 } 36 } 37 for(int i=num[3];i>=1;i--) 38 { 39 if(num[1]>=i) 40 { 41 memcpy(num,nn,sizeof(num)); 42 num[3]-=i; 43 num[1]-=i; 44 dfs6(js+i); 45 memcpy(num,nn,sizeof(num)); 46 } 47 } 48 memcpy(num,nn,sizeof(nn)); 49 dfs6(js); 50 } 51 void dfs4(int js,bool pd){ //4 2 52 if(js>=ans) return; 53 int nn[5]; 54 if(!pd) 55 { 56 memset(num,0,sizeof(num)); 57 for(int i=1;i<=13;i++) num[la[i]]++; 58 memcpy(nn,num,sizeof(num)); 59 for(int i=num[4];i>=1;i--) 60 { 61 if(num[2]>=i*2) 62 { 63 memcpy(num,nn,sizeof(nn)); 64 num[4]-=i; 65 num[2]-=i*2; 66 dfs4(js+i,1); 67 memcpy(num,nn,sizeof(nn)); 68 } 69 } 70 } 71 if(pd) memcpy(nn,num,sizeof(num)); 72 for(int i=num[4];i>=1;i--) 73 { 74 if(num[1]>=i*2) 75 { 76 memcpy(num,nn,sizeof(nn)); 77 num[4]-=i; 78 num[1]-=i*2; 79 dfs5(js+i,0); 80 memcpy(num,nn,sizeof(nn)); 81 } 82 } 83 memcpy(num,nn,sizeof(nn)); 84 dfs5(js,0); 85 } 86 void dfs3(int js){ //1s 87 if(js>=ans) return; 88 int ll[14]; 89 memcpy(ll,la,sizeof(la)); 90 for(int l=12;l>=5;l--) 91 { 92 for(int i=1;i<=12-l+1;i++) 93 { 94 bool yx=1; 95 for(int j=i;j<=i+l-1;j++) 96 { 97 if(la[j]<1) 98 { 99 yx=0; 100 break; 101 } 102 } 103 if(yx) 104 { 105 memcpy(la,ll,sizeof(ll)); 106 for(int j=i;j<=i+l-1;j++) 107 { 108 la[j]-=1; 109 } 110 dfs3(js+1); 111 memcpy(la,ll,sizeof(ll)); 112 } 113 } 114 } 115 memcpy(la,ll,sizeof(ll)); 116 dfs4(js,0); 117 } 118 void dfs2(int js){ //2s 119 if(js>=ans) return; 120 int ll[14]; 121 memcpy(ll,la,sizeof(la)); 122 for(int l=11;l>=3;l--) 123 { 124 for(int i=1;i<=12-l+1;i++) 125 { 126 bool yx=1; 127 for(int j=i;j<=i+l-1;j++) 128 { 129 if(la[j]<2) 130 { 131 yx=0; 132 break; 133 } 134 } 135 if(yx) 136 { 137 memcpy(la,ll,sizeof(ll)); 138 for(int j=i;j<=i+l-1;j++) 139 { 140 la[j]-=2; 141 } 142 dfs2(js+1); 143 memcpy(la,ll,sizeof(ll)); 144 } 145 } 146 } 147 memcpy(la,ll,sizeof(ll)); 148 dfs3(js); 149 } 150 void dfs1(int js){ //3s 151 if(js>=ans) return; 152 int ll[14]; 153 memcpy(ll,la,sizeof(la)); 154 for(int l=7;l>=2;l--) 155 { 156 for(int i=1;i<=12-l+1;i++) 157 { 158 bool yx=1; 159 for(int j=i;j<=i+l-1;j++) 160 { 161 if(la[j]<3) 162 { 163 yx=0; 164 break; 165 } 166 } 167 168 if(yx) 169 { 170 memcpy(la,ll,sizeof(ll)); 171 for(int j=i;j<=i+l-1;j++) 172 { 173 la[j]-=3; 174 } 175 dfs1(js+1); 176 memcpy(la,ll,sizeof(ll)); 177 } 178 } 179 } 180 memcpy(la,ll,sizeof(ll)); 181 dfs2(js); 182 } 183 int main(){ 184 scanf("%d%d",&t,&n); 185 while(t--) 186 { 187 memset(sum,0,sizeof(sum)); 188 memset(la,0,sizeof(la)); 189 memset(num,0,sizeof(num)); 190 ans=0x7fffffff; 191 int a,b,c,d; 192 for(int i=1;i<=n;i++) 193 { 194 int xx,yy; 195 scanf("%d%d",&xx,&yy); 196 if(xx==1) 197 xx=12; 198 else if(xx==2) 199 xx=13; 200 else xx-=2; 201 if(xx==-2) xx=0; 202 sum[xx]++; 203 } 204 memcpy(la,sum,sizeof(sum)); 205 dfs1(0); 206 if(sum[0]) ans++; 207 printf("%dn",ans); 208 } 209 //while(1); 210 return 0; 211 }
- 还没有人评论，欢迎说说您的想法！
客服
