斗地主增强版
多年后发现我的题解被hack了
鄙人在17年10月做了这道题，随手交了一篇题解，之后17年11月参加完noip，从此就退出了oi，一次偶然的机会我又打开了洛谷
没想到我三年前写的题解，过去那么久了，还有人看(竟然还排在了前面，害怕）
首先在这里谢谢大家，有些大佬看了我的代码，指出了我的错误，当时我没有考虑两个三张和两个四张的情况，导致出题人发现了之后，出了个测试点把我的题解给hack了。
这道题算是我oi生涯中做过比较难的题了，当时也比较喜欢玩斗地主这类的扑克游戏，所以肝了好久写的这道题。
当时也没有仔细求证过这个贪心策略是不是一定能给出正确的答案，说是贪心，其实说到底感觉只是把各种特殊情况都列举了一遍，根据自己的打牌经验给了一套感觉正确的出牌方法。然后提交后很幸运的全a掉了（那个时候真的全ac了，不知道什么时候可能出题人发现了我的漏洞，改了测试数据。。。）
当时我看题解里没有我这种方法，就随手交了一篇，没想到过去几年了，会有这么多人看，本人深感抱歉，我随手写的方法可能误导大家了。
下面的代码是根据大佬们的反馈，我修改后的，加了一行特判，又把出题人的测试点水过去了，嘻嘻嘻
#include<iostream>
#include<cstdio>
#include<cstring>
#define gc() getchar()
#define isd isdigit
using namespace std;
int n,t,ans;
int pai[20];//存牌
int san_pai();
void feiji(int step);
void shunzi(int step);
void liandui(int step);
int read() {
int x=0;
char ch=gc();
while(!isd(ch))ch=gc();
while(isd(ch))x=x*10+ch-'0',ch=gc();
return x;
}
void chupai(int step) { //开始出牌
if(step>=ans)return ; //最优性剪枝
int tmp=san_pai(); //打散牌
ans=min(tmp+step,ans); //更新最优解
feiji(step); //飞机
shunzi(step); //顺子
liandui(step);//连对
}
void feiji(int step){//出飞机
int l,end;
for(int st=3; st<=13; ++st) {//枚举连续牌起始点
l=0;
while(pai[st+l]>=3)l++;//找出最大长度
for(int j=l; j>=2; --j) {//枚举出牌长度
end=st+j-1;
for(int k=st; k<=end; k++)pai[k]-=3;//出飞机
chupai(step+1);//继续出牌
for(int k=st; k<=end; k++)pai[k]+=3;//搜索回溯
}
}
return;
}
void liandui(int step) {//连对
int l,end;
for(int st=3; st<=12; ++st) {//枚举连续牌起始点
l=0;
while(pai[st+l]>=2)l++;//找出最大长度
for(int j=l; j>=3; --j) {//枚举出牌长度
end=st+j-1;
for(int k=st; k<=end; k++)pai[k]-=2;//出连对
chupai(step+1);//继续出牌
for(int k=st; k<=end; k++)pai[k]+=2;//搜索回溯
}
}
return;
}
void shunzi(int step) {//顺子
int l,end;
for(int st=3; st<=10; ++st) {//枚举连续牌起始点
l=0;
while(pai[st+l]>=1)l++;//找出最大长度
for(int j=l; j>=5; --j) {
end=st+j-1;
for(int k=st; k<=end; k++)pai[k]-=1;//出顺子
chupai(step+1);//继续出牌
for(int k=st; k<=end; k++)pai[k]+=1;//搜索回溯
}
}
return;
}
int san_pai() {//贪心打散牌
int zs[5],num=0;
memset(zs,0,sizeof(zs));
bool wangzha=false;
if(pai[1]==2)wangzha=true;//是否有王炸
zs[1]+=pai[1]; //王算单牌
for(int i=2; i<=14; ++i)zs[pai[i]]++;//统计个数
/****** 暴力出奇迹 ******/
while(!zs[3]&&zs[1]==1&&zs[2]==1&&zs[4]>1)zs[4]-=2,zs[1]--,zs[2]--,num+=2;//神特判
//把一个炸拆成3张和单牌,再出一组四带二单和三带一
while(!zs[2]&&zs[1]==1&&zs[4]==1&&zs[3]>1)zs[3]-=2,zs[1]--,zs[4]--,num+=2;//神特判
//把一组三张拆成一对和一单,再出一组四带二单和三带二
if(zs[3]+zs[4]>zs[1]+zs[2])//三四张的比单牌和对牌多,拆着打
while(zs[4]&&zs[2]&&zs[3])zs[2]--,zs[3]--,zs[1]++,zs[4]--,num++;//拆三张,4带两对余一单
if(zs[3]+zs[4]>zs[1]+zs[2])//还多继续拆
while(zs[4]&&zs[1]&&zs[3])zs[1]--,zs[3]--,zs[2]++,zs[4]--,num++;//拆三张,4带两单余一对
while(zs[4]&&zs[1]>1)zs[4]--,zs[1]-=2,num++;//四带两单
while(zs[4]&&zs[2]>1)zs[4]--,zs[2]-=2,num++;//四带两对
while(zs[4]&&zs[2] )zs[4]-- ,zs[2]--,num++;//对看成两单再四带
if(zs[3]%3==0&&zs[1]+zs[2]<=1) //三张的太多了拆三张
while(zs[3]>2)zs[3]-=3,num+=2;//把一组三张拆成单和对,再出三带一和三带二
while(zs[3]&&zs[1] )zs[3]-- ,zs[1]--,num++;//三带一
while(zs[3]&&zs[2] )zs[3]-- ,zs[2]--,num++;//三带二
//还剩三张和炸,组合出
while(zs[3]==zs[4]&&zs[3]%2==0&&zs[3]){num+=2;zs[3]-=2;zs[4]-=2;}//新加的，两三两四把三张全拆开，能2步出完
while(zs[4]>1&&zs[3])zs[3]--,zs[4]-=2,num+=2;//把一个炸拆成一对和两单,再出三带二和四带两单
while(zs[3]>1&&zs[4])zs[4]--,zs[3]-=2,num+=2;//把一个炸拆成两对,再出两组三带一对
while(zs[3]>2)zs[3]-=3,num+=2; //同上,把一组三张拆成单和对,再出三带一和三带二
while(zs[4]>1)zs[4]-=2,num++; //把一个炸拆成两对,再出一组四带两对
if(wangzha&&zs[1]>=2)//有王炸并且没被带跑
return num+zs[2]+zs[3]+zs[4]+zs[1]-1;//双王一块出
else
return num+zs[1]+zs[2]+zs[3]+zs[4];//出剩余的牌,返回答案
}
int main() {
t=read();
n=read();
int a,b;
while(t--) {
ans=0x7f7f7f7f;
memset(pai,0,sizeof(pai));
for(int i=1; i<=n; ++i) {
a=read();b=read();
if(a==1)pai[14]++; //14代表A
else if(a==0)pai[1]++;//1代表王
else pai[a]++;
}
chupai(0);
printf("%d\n",ans);
}
}大家看完娱乐了一下就好，不是很具有做题的指导意义，建议大家学学dp的解法，dp是个好算法。
最后谢谢朋友们！
之前存在漏洞的题解：题解 P2540 【斗地主增强版】