题解 P2668 【斗地主】
MorsLin
2018-05-02 19:03:13
### 毒瘤题目,搞了三天……
----
也没什么好讲的，就是纯搜索，先搜顺子，再搜其他的，最后单张牌和对子的时候，就不要搜索了，直接枚举，不然会T飞掉~~多么痛的领悟~~……
主要还是靠码力
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t,n;
int card[25],sp[25],ans=0x7fffff;
int x;
inline int read()
{
int k=0,f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-')
f=-1;
for(;isdigit(c);c=getchar())
k=(k<<3)+(k<<1)+c-48;
return k*f;
}
void dfs(int sum,int step)
{
if(sum<0||step>=ans)
return;
if(sum==0)
{
ans=min(ans,step);
return ;
}
//============顺子
int flag[101]={0},tot=0,pc[101]={0};
flag[3]=flag[2]=flag[1]=0; tot=0;
for(int i=3;i<=14;i++)
{
if(card[i]>=3)
{
flag[3]++;
pc[++tot]=i;
}
else
{
flag[3]=0;
tot=0;
continue;
}
if(flag[3]>=2)
{
for(int j=1;j<=tot;j++)
{
card[pc[j]]-=3;
}
dfs(sum-3*tot,step+1);
for(int j=1;j<=tot;j++)
{
card[pc[j]]+=3;
}
}
}
tot=0;
for(int i=3;i<=14;i++)
{
if(card[i]>=2)
{
flag[2]++;
pc[++tot]=i;
}
else
{
flag[2]=0;
tot=0;
continue;
}
if(flag[2]>=3)
{
for(int j=1;j<=tot;j++)
{
card[pc[j]]-=2;
}
dfs(sum-2*tot,step+1);
for(int j=1;j<=tot;j++)
{
card[pc[j]]+=2;
}
}
}
tot=0;
for(int i=3;i<=14;i++)
{
if(card[i]>=1)
{
flag[1]++;
pc[++tot]=i;
}
else
{
flag[1]=0;
tot=0;
continue;
}
if(flag[1]>=5)
{
for(int j=1;j<=tot;j++)
{
card[pc[j]]-=1;
}
dfs(sum-tot,step+1);
for(int j=1;j<=tot;j++)
{
card[pc[j]]+=1;
}
}
}
//========四带
flag[11]=flag[12]=0;
for(int i=3;i<=15;i++)
{
if(card[i]>=4)
{
card[i]-=4;
for(int j=0;j<=15;j++)
{
if(card[j]>=4)
{
card[j]-=4;
dfs(sum-8,step+1);
card[j]+=4;
}
if(card[j]>=2)
{
card[j]-=2;
for(int k=3;k<=15;k++)
{
if(card[k]>=2)
{
card[k]-=2;
dfs(sum-8,step+1);
card[k]+=2;
}
}
dfs(sum-6,step+1);
card[j]+=2;
}
if(card[j]>0)
{
for(int k=0;k<15;k++)
{
if(card[k]>0)
{
if(j==k)
continue;
card[j]-=1; card[k]-=1;
dfs(sum-6,step+1);
card[j]+=1; card[k]+=1;
}
}
}
}
dfs(sum-4,step+1);
card[i]+=4;
}
}
//======三带
flag[11]=flag[12]=0;
for(int i=1;i<=15;i++)
{
if(card[i]>=3)
{
card[i]-=3;
for(int j=0;j<=15;j++)
{
if(i==j)
continue;
if(card[j]>=1)
{
card[j]-=1;
dfs(sum-4,step+1);
card[j]+=1;
}
if(card[j]>=2&&j!=0)
{
card[j]-=2;
dfs(sum-5,step+1);
card[j]+=2;
}
}
dfs(sum-3,step+1);
card[i]+=3;
}
}
//单张+对子
flag[32]=0,flag[5]=0;
for(int i=0;i<=15;i++)
{
if(card[i]==2)
{
flag[5]++;
}
if(card[i]==1)
{
flag[32]++;
}
}
if(sum-2*flag[5]-flag[32]==0)
ans=min(ans,step+flag[5]+flag[32]);
}
int main()
{
t=read(),n=read();
while(t--)
{
ans=0x7fffff;
memset(card,0,sizeof(card));
for(int i=1;i<=n;i++)
{
int col,x;
x=read(),col=read();
if(x==1||x==2)
card[13+x]++;
else
card[x]++;
}
dfs(n,0);
printf("%d\n",ans);
}
return 0;
}
```