调了快 3 个小时了,救救孩子吧!!!
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int t,n,a,b;
int ans;
int card[25];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
void dfs(int x){//x表示当前的出牌次数
if(x>=ans){
return;
}
//先出单顺子(不包括2点和双王)
int k=0;//k表示当前扔出的牌数
for (int i=3;i<=14;i++){
if(card[i]==0){
k=0;//断了
}
else{
k++;//多了一个牌
if(k>=5){//单顺子至少出5张
for (int j=i;j>=i-k+1;j--){//因为是连续的
card[j]--;//出牌
}
dfs(x+1);//继续搜索
for (int j=i;j>=i-k+1;j--){
card[j]++;//回溯
}
}
}
}
//2.出双顺子(不包括2点和双王)
k=0;//这里记录几组
for (int i=3;i<=14;i++){
if(card[i]<=1){
k=0;//断了
}
else{
k++;
if(k>=3){//至少有3对
for (int j=i;j>=i-k+1;j--){
card[j]-=2;
}//出牌
dfs(x+1);
for (int j=i;j>=i-k+1;j--){
card[j]+=2;
}
}
}
}
//3.出三顺子(不包括2点和双王)
k=0;//这里记录三张牌的出现的次数
for (int i=3;i<=14;i++){
if(card[i]<=2){
k=0;
}
else{
k++;
if(k>=2){
for (int j=i;j>=i-k+1;j--){
card[j]-=3;
}
dfs(x+1);
for (int j=i;j>=i-j+1;j--){
card[j]+=3;
}
}
}
}
//4出带牌(单张可以带大小王)
for (int i=2;i<=14;i++){
if(card[i]<=3){//三带一
if(card[i]<=2){
continue;
}
card[i]-=3;
for (int j=2;j<=15;j++){//出单牌
if(card[j]<=0||i==j){
continue;
}
card[j]--;
dfs(x+1);
card[j]++;
}
for (int j=2;j<=14;j++){//出对牌
if(card[j]<=1||j==i){
continue;
}
card[j]-=2;
dfs(x+1);
card[j]+=2;
}
card[i]+=3;
}
else{//大于三张牌的可以选择4张牌或者3张牌
card[i]-=3;//3带的
for (int j=2;j<=15;j++){//出单牌
if(card[j]<=0||j==i){
continue;
}
card[j]--;
dfs(x+1);
card[j]++;
}
for (int j=2;j<=14;j++){//出对牌
if(card[j]<=1||i==j){
continue;
}
card[j]-=2;
dfs(x+1);
card[j]+=2;
}
card[i]+=3;
card[i]-=4;//4张牌带的
for (int j=2;j<=15;j++){//带两个单张
if(card[j]<=0||j==i){
continue;
}
card[j]--;
for (int k=2;k<=15;k++){
if(card[k]<=0||k==j){
continue;
}
card[k]--;
dfs(x+1);
card[k]++;
}
card[j]++;
}
for (int j=2;j<=14;j++){//带两个对
if(card[j]<=1||i==j){
continue;
}
card[j]-=2;
for (int k=2;k<=14;k++){
if(k==i||card[k]<=1){
continue;
}//一对牌可以算两张牌
card[k]-=2;
dfs(x+1);
card[k]+=2;
}
card[j]+=2;
}
card[i]+=4;
}
}
//cout<<1<<"\n";
for (int i=2;i<=15;i++){//把剩下的牌出完
if(card[i]){
x++;
}//由于大小王和对子可以同时出,所以算一次
}
ans=min(ans,x);
}
int main(){
t=read();
n=read();
while(t--){
ans=0x7fffffff;
memset(card,0,sizeof(card));
for (int i=1;i<=n;i++){
a=read();
b=read();
if(a==1){
card[14]++;
}//处理A牌
else if(a==0){
card[15]++;
}//处理大小王,当做双牌处理即可
else card[a]++;
}
dfs(0);
write(ans);
printf("\n");
}
return 0;
}
测评记录:here
如果是剪枝的问题,请指出,或是代码逻辑错误,谢谢了。