【BZOJ4325】NOIP2015 斗地主
Description
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：
Input
第一行包含用空格隔开的2个正整数T,N，表示手牌的组数以及每组手牌的张数。
接下来T组数据，每组数据N行，每行一个非负整数对Ai,Bi，表示一张牌，其中Ai表示牌的数码,Bi表示牌的花色，中间用空格隔开。特别的，我们用1来表示数码A，11表示数码J，12表示数码Q，13表示数码K；黑桃、红心、梅花、方片分别用1-4来表示；小王的表示方法为01，大王的表示方法为02。
Output
共T行，每行一个整数，表示打光第T组手牌的最少次数。
Sample Input
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
Sample Output
3
HINT
共有1组手牌，包含8张牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A以及黑桃A。可以通过打单顺子（方片7，方片8，黑桃9，方片10，黑桃J），单张牌（黑桃5）以及对子牌（黑桃A以及方片A）在3次内打光。
T<=10
N<=23
题解：直接搜索。。。由于先甩龙和多带多肯定比先甩单和对强，所以先从龙判断，并且龙最好从长的龙开始判断。
然后如何甩几带几呢？这时的牌的大小已经没用了，我们可以直接用s[i]表示数量为i的牌有多少种，然后贪心的按4+2+2,4+1+1,3+2,3+1的顺序选就行了。
然而。。。对于本题来说，双王不能成对，王可以当成单，四张牌不能拆成两个对。。。
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
int n,m,ans,cnt;
int v[20],s[20];
char str[10];
void dfs(int dep)
{
if(!cnt)
{
ans=min(ans,dep);
return ;
}
if(dep+1>=ans) return ;
int i,j;
if(v[14]&&v[15])
{
v[14]--,v[15]--,cnt-=2,dfs(dep+1),v[14]++,v[15]++,cnt+=2;
if(ans==dep+1) return ;
}
if(cnt>=6) //3龙
{
for(i=1;i<=11;i++) if(v[i]>=3&&v[i+1]>=3)
{
v[i]-=3,cnt-=3;
for(j=i+1;j<=12&&v[j]>=3;j++) v[j]-=3,cnt-=3;
for(j=j-1;j>=i+1;j--) dfs(dep+1),v[j]+=3,cnt+=3;
v[i]+=3,cnt+=3;
if(ans==dep+1) return ;
}
}
if(cnt>=6) //2龙
{
for(i=1;i<=10;i++) if(v[i]>=2&&v[i+1]>=2&&v[i+2]>=2)
{
v[i]-=2,v[i+1]-=2,cnt-=4;
for(j=i+2;j<=12&&v[j]>=2;j++) v[j]-=2,cnt-=2;
for(j=j-1;j>=i+2;j--) dfs(dep+1),v[j]+=2,cnt+=2;
v[i]+=2,v[i+1]+=2,cnt+=4;
if(ans==dep+1) return ;
}
}
if(cnt>=5) //1龙
{
for(i=1;i<=8;i++) if(v[i]&&v[i+1]&&v[i+2]&&v[i+3]&&v[i+4])
{
v[i]--,v[i+1]--,v[i+2]--,v[i+3]--,cnt-=4;
for(j=i+4;j<=12&&v[j];j++) v[j]--,cnt--;
for(j=j-1;j>=i+4;j--) dfs(dep+1),v[j]++,cnt++;
v[i]++,v[i+1]++,v[i+2]++,v[i+3]++,cnt+=4;
if(ans==dep+1) return ;
}
}
memset(s,0,sizeof(s));
for(i=1;i<=15;i++) s[v[i]]++;
while(s[4])
{
s[4]--,dep++;
if(s[2]>=2) s[2]-=2;
else if(s[1]>=2) s[1]-=2;
}
while(s[3])
{
s[3]--,dep++;
if(s[2]) s[2]--;
else if(s[1]) s[1]--;
}
dep+=s[2]+s[1]-(s[1]>=2&&v[14]&&v[15]);
ans=min(ans,dep);
}
void work()
{
ans=1<<30;
int i,a,b;
memset(v,0,sizeof(v));
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
if(!a) a=b+13;
if(a==1) a=12;
else if(a==2) a=13;
else if(a<=13) a-=2;
v[a]++;
}
cnt=n;
dfs(0);
printf("%d\n",ans);
return ;
}
int main()
{
int T;
scanf("%d%d",&T,&n);
while(T--) work();
return 0;
}