2015D1T3 斗地主
problem
斗地主是一种使用黑桃、红心、梅花、方片的(A)到(K)加上大小王的共(54)张牌来进行的扑克牌游戏。在斗地主中，牌的大小关 系根据牌的数码表示如下：(3<4<5<6<7<8<9<10<J<Q<K<A<2< ext{小王}< ext{大王})，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 (n) 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。 现在对于若干组手牌，分别最少需要多少次出牌可以将它们打光。 需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：
第一行包含用空格隔开的2个正整数 (T,n) ，表示手牌的组数以及每组手牌的张数。 接下来 (T) 组数据，每组数据 (n) 行，每行一个非负整数对 (a_i,b_i) ，表示一张牌，其中 (a_i) 表示牌的数码， (b_i) 表示牌的花色，中间用空格隔开。特别的，我们用 (1) 来表示数码 (A)， (11) 表示数码$ J$， (12) 表示数码$ Q$， (13) 表示数码 (K)；黑桃、红心、梅花、方片分别用 (1-4) 来表示；小王的表示方法为 (01) ，大王的表示方法为 (02) 。
输出共 (T) 行，每行一个整数，表示打光第 (i) 组手牌的最少次数。
solution
一个奇妙的爆搜。我觉得这是一道绝妙的搜索进阶模板。其实代码特别好懂。这种牌类游戏可能记录每种牌的个数会比记录点数好一些。
code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int read(){
int a=0,op=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') op=-1;c=getchar();}
while(c>='0'&&c<='9'){a*=10,a+=c^48,c=getchar();}
return a*op;
}
int T,ans,n,sum[25];
void dfs(int x){//x为出牌次数
if(x>=ans) return ;
int k=0;
for(int i=3;i<=14;i++){
if(sum[i]==0) k=0;
else {
k++;
if(k>=5){
for(int j=i;j>=i-k+1;j--) sum[j]--;
dfs(x+1);
for(int j=i;j>=i-k+1;j--) sum[j]++;
}
}
}
k=0;//双顺子
for(int i=3;i<=14;i++){
if(sum[i]<=1) k=0;
else {
k++;
if(k>=3){
for(int j=i;j>=i-k+1;j--) sum[j]-=2;
dfs(x+1);
for(int j=i;j>=i-k+1;j--) sum[j]+=2;
}
}
}
k=0;//三顺子
for(int i=3;i<=14;i++){
if(sum[i]<=2) k=0;
else {
k++;
if(k>=2){
for(int j=i;j>=i-k+1;j--) sum[j]-=3;
dfs(x+1);
for(int j=i;j>=i-k+1;j--) sum[j]+=3;
}
}
}
k=0;//带牌
for(int i=2;i<=14;i++){
if(sum[i]<=3){
if(sum[i]<=2) continue;
sum[i]-=3;
for(int j=2;j<=15;j++){
if(sum[j]<=0||j==i) continue;//没有牌带
sum[j]--;
dfs(x+1);
sum[j]++;
}
for(int j=2;j<=15;j++){
if(sum[j]<=1||j==i) continue;//没有牌带
sum[j]-=2;
dfs(x+1);
sum[j]+=2;
}
sum[i]+=3;
}
else{
sum[i]-=3;
for(int j=2;j<=15;j++){
if(sum[j]<=0||j==i) continue;
sum[j]--;dfs(x+1);sum[j]++;
}
for(int j=2;j<=14;j++){
if(sum[j]<=1||j==i) continue;
sum[j]-=2;dfs(x+1);sum[j]+=2;
}
sum[i]+=3;
sum[i]-=4;
for(int j=2;j<=15;j++){
if(sum[j]<=0||j==i) continue;//不能自己带自己
sum[j]--;
for(int k=2;k<=15;k++){
if(sum[k]<=0||j==k) continue;
sum[k]--;
dfs(x+1);
sum[k]++;
}
sum[j]++;
}
for(int j=2;j<=14;j++){
if(sum[j]<=1||j==i) continue;
sum[j]-=2;
for(int k=2;k<=14;k++){
if(sum[k]<=1||j==k) continue;
sum[k]-=2;
dfs(x+1);
sum[k]+=2;
}
sum[j]+=2;
}
sum[i]+=4;
}
}
for(int i=2;i<=15;i++) if(sum[i]) x++;
ans=min(ans,x);
}
int main(){
T=read(),n=read();
while(T--){
ans=0x7fffffff;
int x,y;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++){
x=read(),y=read();
if(x==0) sum[15]++;
else if(x==1) sum[14]++;
else sum[x]++;
}
dfs(0);
printf("%d
",ans);
}
return 0;
}
斗地主加强版
原样交上去82分。有WA有TLE。
暴力搜顺子
为什么顺子要暴力？并不是出越长的顺子越好，如果你有一组手牌，3,4,5,6,7,6,7,8,9,10，你一下把最长的出了去，你会单两张牌，不如出两个顺子，所以顺子要暴力。
贪心打散牌
这是核心所在，也是不超时的原因。
可以先统计一下不同牌个数的组数，然后再出牌，
那如何打出最优解？
首先一定要先出四带二，再出三带一，这是很容易想到的，因为四带可以带走两张。
这样写正的行了吗？
当然不行，原题的随机数额可以过，增强版的必须考虑拆牌，而且还要考虑王炸的特殊情况，王算单牌，但可以当对出，明确这一点。
拆牌
什么时候该拆牌呢，对牌除了四带的情况不能拆，因为拆了可能多打一手牌。
仔细想想，三张和炸在单牌和对牌很多的时候是不能拆的，拆了就多大。
当单牌和对牌数的和小于三张和炸的和，这就可以拆了
因为这时不拆的话没得带，只能单出，如果把三张拆成一单和一对，让其余的三张和炸带走，就会少一步。
四张的同理。
#include <bits/stdc++.h>
using namespace std;
int n,T,d[5],c[20],a,b,kin,ans,tot,mn;
int read(){
int a=0,op=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') op=-1;c=getchar();}
while(c>='0'&&c<='9'){a*=10,a+=c^48,c=getchar();}
return a*op;
}
int gao()
{
int res=0,e[5];memcpy(e,d,sizeof(e));//做完之后要还原，备份一份d数组
while(d[4])
{
if(d[1]<2&&!d[2]) break;//不能四带二了
if(d[1]>=2) d[4]--,d[1]-=2,res++;//带两个单牌
else if(d[2]>=2) d[4]--,d[2]-=2,res++;//带两个对子
else if(d[2]==1) d[4]--,d[2]--,res++;//带一个对子（优先级最低）
}
while(d[3])
{
if(!d[1]&&!d[2]) break;//不能三带了
if(d[1]) d[3]--,d[1]--,res++;//带一个单牌
else if(d[2]) d[3]--,d[2]--,res++;//带一个对子
}
int g=d[1]+d[2]+d[3]+d[4]+res;//总出牌次数
memcpy(d,e,sizeof(e));return g;//还原
}
void dfs2()
{
tot=min(tot,gao());//即时统计答案
if(d[3]) d[3]--,d[1]++,d[2]++,dfs2(),d[3]++,d[1]--,d[2]--;//把三张牌拆成一个单牌和一个对子（33344445555）
if(d[4]) d[4]--,d[2]++,d[2]++,dfs2(),d[4]++,d[2]--,d[2]--;//把四张牌拆成两个对子（33334444）
if(d[4]) d[4]--,d[1]++,d[3]++,dfs2(),d[4]++,d[1]--,d[3]--;//把四张牌拆成一个单牌和一个三对（33334444556）
}
void dfs1(int val)
{
memset(d,0,sizeof(d));for(int i=2;i<=16;i++) d[c[i]]++;//统计不同大小的牌的出现次数
tot=1e9;dfs2();ans=min(ans,val+tot);//即时更新答案
for(int i=3;i<=10;i++) if(c[i]>=1) for(int j=i+1;j<=14;j++)//出单顺
{
if(c[j]<1) break;if(j-i<4) continue;
for(int k=i;k<=j;k++) c[k]-=1;dfs1(val+1);for(int k=i;k<=j;k++) c[k]+=1;
}
for(int i=3;i<=12;i++) if(c[i]>=2) for(int j=i+1;j<=14;j++)//出双顺
{
if(c[j]<2) break;if(j-i<2) continue;
for(int k=i;k<=j;k++) c[k]-=2;dfs1(val+1);for(int k=i;k<=j;k++) c[k]+=2;
}
for(int i=3;i<=13;i++) if(c[i]>=3) for(int j=i+1;j<=14;j++)//出三顺
{
if(c[j]<3) break;if(j-i<1) continue;
for(int k=i;k<=j;k++) c[k]-=3;dfs1(val+1);for(int k=i;k<=j;k++) c[k]+=3;
}
}
int main()
{
for(scanf("%d%d",&T,&n);T--;)
{
memset(c,0,sizeof(c));mn=1e9;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
if(a==0&&b==1) c[15]++;
else if(a==0&&b==2) c[16]++;//大小王
else if(a==1) c[14]++;
else if(a>1) c[a]++;//对A进行处理，方便出顺子
}
kin=min(c[15],c[16]);
c[15]-=kin;c[16]-=kin;//出王炸（333大小王）
ans=1e9;dfs1(0);mn=min(mn,kin+ans);
c[15]+=kin;c[16]+=kin;//不出王炸（3333大小王）
ans=1e9;dfs1(0);mn=min(mn,ans);
printf("%d
",mn);
}
}