思路
存储
v[]数组存储各牌型的数量。
v[3]~v[13]存储 3-K 的牌数。v[14]，v[15]存 A，2 的牌数。v[16]，v[17]存小大王。
暴力出奇迹
主体使用 dfs 爆搜解决（什么贪心，什么 dp，不用！）。
打牌顺序：顺子与几带几 -> 剩下的牌。
三带 X：
for(int i=3;i<=15;i++)//大小王最多有一张
if(v[i]>=3)//三
for(int j=3;j<=17;j++)
if(i!=j)//不能自己带♂自己
{
if(v[j]>=1)
v[i]-=3,v[j]-=1,dfs(num+1),v[i]+=3,v[j]+=1;//带一
if(v[j]>=2)
v[i]-=3,v[j]-=2,dfs(num+1),v[i]+=3,v[j]+=2;//带对
}//对称美
/*
num是当前的打牌次数
记得回溯！
*/
四带二 X：
for(int i=3;i<=15;i++)
if(v[i]>=4)//四
for(int j=3;j<=17;j++)
for(int k=j;k<=17;k++)
if(i!=j&&i!=k)
{
if(v[j]>=1&&v[k]>=1)
v[i]-=4,v[j]-=1,v[k]-=1,dfs(num+1),v[i]+=4,v[j]+=1,v[k]+=1;//带二单
if(v[j]>=2&&v[k]>=2)
v[i]-=4,v[j]-=2,v[k]-=2,dfs(num+1),v[i]+=4,v[j]+=2,v[k]+=2;//带二对
}
顺子：
cnt=0;//牌数
for(int j=i;j<=14;j++)
{
if(v[j]>=1)
cnt++;
else
break;
if(cnt>=5)
{
for(int k=i;k<=i+cnt-1;k++)
v[k]-=1;
dfs(num+1);
for(int k=i;k<=i+cnt-1;k++)
v[k]+=1;
}
}
连对、三连不赘述了。
出剩余牌：
for(int i=3;i<=17;i++)
if(v[i])
num++;//单牌、对子、三张、炸弹都包括在内
ans=min(ans,num);//取最优
CODE
拼在一起，就是：
#include<bits/stdc++.h>
using namespace std;
int T,n,ans,v[100];
void dfs(int num)
{
int cnt=0;
if(num>=ans)//最优化剪枝
return;
if(v[16]>=1&&v[17]>=1)
v[16]-=1,v[17]-=1,dfs(num+1),v[16]+=1,v[17]+=1;//火箭
for(int i=3;i<=15;i++)
{
if(v[i]>=3)//三
for(int j=3;j<=17;j++)
if(i!=j)
{
if(v[j]>=1)
v[i]-=3,v[j]-=1,dfs(num+1),v[i]+=3,v[j]+=1;//带一
if(v[j]>=2)
v[i]-=3,v[j]-=2,dfs(num+1),v[i]+=3,v[j]+=2;//带对
}
if(v[i]>=4)//四
for(int j=3;j<=17;j++)
for(int k=j;k<=17;k++)
if(i!=j&&i!=k)
{
if(v[j]>=1&&v[k]>=1)
v[i]-=4,v[j]-=1,v[k]-=1,dfs(num+1),v[i]+=4,v[j]+=1,v[k]+=1;//带二单
if(v[j]>=2&&v[k]>=2)
v[i]-=4,v[j]-=2,v[k]-=2,dfs(num+1),v[i]+=4,v[j]+=2,v[k]+=2;//带二对
}
cnt=0;
for(int j=i;j<=14;j++)
{
if(v[j]>=1)
cnt++;
else
break;
if(cnt>=5)//顺子
{
for(int k=i;k<=i+cnt-1;k++)
v[k]-=1;
dfs(num+1);
for(int k=i;k<=i+cnt-1;k++)
v[k]+=1;
}
}
cnt=0;
for(int j=i;j<=14;j++)
{
if(v[j]>=2)
cnt++;
else
break;
if(cnt>=3)//连对
{
for(int k=i;k<=i+cnt-1;k++)
v[k]-=2;
dfs(num+1);
for(int k=i;k<=i+cnt-1;k++)
v[k]+=2;
}
}
cnt=0;
for(int j=i;j<=14;j++)
{
if(v[j]>=3)
cnt++;
else
break;
if(cnt>=2)//三连
{
for(int k=i;k<=i+cnt-1;k++)
v[k]-=3;
dfs(num+1);
for(int k=i;k<=i+cnt-1;k++)
v[k]+=3;
}
}
}
for(int i=3;i<=17;i++)
if(v[i])
num++;
ans=min(ans,num);
return;
}
int main()
{
scanf("%d%d",&T,&n);
while(T--)
{
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(a>=3&&a<=13)//3~K
v[a]++;
else if(a>=1&&a<=2)//A~2
v[13+a]++;
else
if(b==1)
v[16]++;//joker
else
v[17]++;//JOKER
}
ans=n;
dfs(0);
printf("%d\n",ans);
}
return 0;
}
优化
我们可以发现，出牌顺序对问题的解无影响。
所以，可以化排列为组合，在 dfs 时可剪去大量冗余运算。
#include<bits/stdc++.h>
using namespace std;
int T,n,ans,v[100];
void dfs(int num,int now)
{
int cnt=0;
if(num>=ans||now>17)
return;
if(v[16]>=1&&v[17]>=1)
v[16]-=1,v[17]-=1,dfs(num+1,now),v[16]+=1,v[17]+=1;//火箭
for(int i=now;i<=15;i++)
{
if(v[i]>=3)//三
for(int j=3;j<=17;j++)
if(i!=j)
{
if(v[j]>=1)
v[i]-=3,v[j]-=1,dfs(num+1,i),v[i]+=3,v[j]+=1;//带一
if(v[j]>=2)
v[i]-=3,v[j]-=2,dfs(num+1,i),v[i]+=3,v[j]+=2;//带对
}
if(v[i]>=4)//四
for(int j=3;j<=17;j++)
for(int k=j;k<=17;k++)
if(i!=j&&i!=k)
{
if(v[j]>=1&&v[k]>=1)
v[i]-=4,v[j]-=1,v[k]-=1,dfs(num+1,i),v[i]+=4,v[j]+=1,v[k]+=1;//带二单
if(v[j]>=2&&v[k]>=2)
v[i]-=4,v[j]-=2,v[k]-=2,dfs(num+1,i),v[i]+=4,v[j]+=2,v[k]+=2;//带二对
}
cnt=0;
for(int j=i;j<=14;j++)
{
if(v[j]>=1)
cnt++;
else
break;
if(cnt>=5)//顺子
{
for(int k=i;k<=i+cnt-1;k++)
v[k]-=1;
dfs(num+1,i);
for(int k=i;k<=i+cnt-1;k++)
v[k]+=1;
}
}
cnt=0;
for(int j=i;j<=14;j++)
{
if(v[j]>=2)
cnt++;
else
break;
if(cnt>=3)//连对
{
for(int k=i;k<=i+cnt-1;k++)
v[k]-=2;
dfs(num+1,i);
for(int k=i;k<=i+cnt-1;k++)
v[k]+=2;
}
}
cnt=0;
for(int j=i;j<=14;j++)
{
if(v[j]>=3)
cnt++;
else
break;
if(cnt>=2)//三连
{
for(int k=i;k<=i+cnt-1;k++)
v[k]-=3;
dfs(num+1,i);
for(int k=i;k<=i+cnt-1;k++)
v[k]+=3;
}
}
}
for(int i=3;i<=17;i++)
if(v[i])
num++;//剩余牌
ans=min(ans,num);
return;
}
int main()
{
scanf("%d%d",&T,&n);
while(T--)
{
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(a>=3&&a<=13)//3~K
v[a]++;
else if(a>=1&&a<=2)//A~2
v[13+a]++;
else
if(b==1)
v[16]++;//joker
else
v[17]++;//JOKER
}
ans=n;
dfs(0,3);
printf("%d\n",ans);
}
return 0;
}
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/87780d906543/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
