P2431 - 【NOIP2015】斗地主
Description
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种 使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如 下：3＜4＜5＜6＜7＜8＜9＜10＜J＜Q＜K＜A＜2＜小王＜大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由n张牌组成。游戏者每 次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。
现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
具体规则如下：
Input
第一行包含用空格隔开的2个正整数Tn，表示手牌的组数以及每组手牌的张数。
接下来T组数据，每组数据n行，每行一个非负整数对aibi表示一张牌，其中ai示牌的数码，bi表示牌的花色，中间用空格隔开。
特别的，我们用1来表示数码A，11表示数码J，12表示数码Q，13表示数码K；黑桃、红心、梅花、方片分别用1-4来表示；小王的表示方法为01，大
王的表示方法为02。
Output
共T行，每行一个整数，表示打光第i手牌的最少次数。
Sample Input
样例输入1:
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
样例输入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
Sample Output
样例输出1：
3
样例输出2：
6
贪心的想想，最好是先一次性出多点． 所以先打三顺子，再打双顺子，再打单顺子． 然后剩余的牌直接按照出牌的数量从大到小打． 因为能够打四带两对肯定打掉四带两对最优。
注意搜顺子的时候不一定要把顺子全部打出去． 因为可能把顺子直接打出去之后剩的都是单牌了。 然后很坑的是， 要把王炸看成一对牌，就是说王炸可以被带出去？！？！？！．
1 #include<set> 2 #include<map> 3 #include<queue> 4 #include<stack> 5 #include<ctime> 6 #include<cmath> 7 #include<string> 8 #include<vector> 9 #include<cstdio> 10 #include<cstdlib> 11 #include<cstring> 12 #include<iostream> 13 #include<algorithm> 14 using namespace std; 15 int sum[20],ans=100,c[10]; 16 int IDA_star() 17 { 18 memset(c,0,sizeof(c)); 19 int tot=0; 20 for(int i=1;i<=14;i++) c[sum[i]]++; 21 while(c[4] && c[2]>1) c[4]--,c[2]-=2,tot++; 22 while(c[4] && c[1]>1) c[4]--,c[1]-=2,tot++; 23 while(c[4] && c[2]) c[4]--,c[2]--,tot++; 24 while(c[3] && c[2]) c[3]--,c[2]--,tot++; 25 while(c[3] && c[1]) c[3]--,c[1]--,tot++; 26 return tot+c[1]+c[2]+c[3]+c[4]; 27 } 28 void search(int step) 29 { 30 if(step>=ans) return; 31 for(int i=1;i<=11;i++) //三顺子 32 { 33 int j;if(sum[i]<3) continue; 34 for(j=i;sum[j]>=3 && j<=12;j++); 35 j--; 36 if(j-i+1>=2){ 37 for(int j2=i+1;j2<=j;j2++){ 38 for(int k=i;k<=j2;k++) sum[k]-=3; 39 search(step+1); 40 for(int k=i;k<=j2;k++) sum[k]+=3; 41 } 42 } 43 } 44 for(int i=1;i<=10;i++) //双顺子 45 { 46 int j;if(sum[i]<2) continue; 47 for(j=i;sum[j]>=2 && j<=12;j++); 48 j--; 49 if(j-i+1>=3){ 50 for(int j2=i+2;j2<=j;j2++){ 51 for(int k=i;k<=j2;k++) sum[k]-=2; 52 search(step+1); 53 for(int k=i;k<=j2;k++)sum[k]+=2; 54 } 55 } 56 } 57 for(int i=1;i<=8;i++) //单顺子 58 { 59 int j;if(sum[i]<1) continue; 60 for(j=i;sum[j]>=1 && j<=12;j++); 61 j--; 62 if(j-i+1>=5){ 63 for(int j2=i+4;j2<=j;j2++){ 64 for(int k=i;k<=j2;k++) sum[k]--; 65 search(step+1); 66 for(int k=i;k<=j2;k++) sum[k]++; 67 } 68 } 69 } 70 int cut=IDA_star(); 71 if(step+cut>=ans) return; 72 else ans=step+cut; 73 } 74 int main() 75 { 76 freopen("!.in","r",stdin); 77 freopen("!.out","w",stdout); 78 int T,n; 79 scanf("%d%d",&T,&n); 80 while(T){ 81 ans=100; 82 memset(sum,0,sizeof(sum)); 83 T--;int x,y; 84 for(int i=1;i<=n;i++){ 85 scanf("%d%d",&x,&y); 86 if(x==0) sum[14]++; 87 else sum[((x+10)%13)+1]++; 88 } 89 search(0); 90 printf("%d ",ans); 91 } 92 return 0; 93 }