这道题做的时候让我几近崩溃,因为如果要打暴力的话太烦了不想打 。
但是我们发现:
这样只要判断前六种方法就行了,打几个判断,30~
首先,做一下基本处理(简化题目):
因为一般的斗地主除了大王小王,没有花色的大小区别,但这里也不是让你赢,只是自己一个人快速打光牌。
我们发现花色并没有什么用,可以免去。
所以我们我们用一个桶
来存每张牌。
但,众所周知,虽然A是1,2是2,大小王是0,但其它牌<A<2<小王<大王。
所以应该把读入顺序改一下:
A为12,2为13,大小王为14;其它减2,填上A,2的空。
这样,就保存下了牌。
接下来,我们可以用一个递归枚举顺子,递归参数存出顺子的数量。
我们很容易得到:
1.除顺子外,出的牌越多越好。(即能N带N,自然带上)
2.有时候不出顺子比除顺子好。
所以我们每次先把不出顺子的出牌次数求出。(即按四带两对——>四带二——>三带二——>三带一的顺序打)
然后判断当前 不出顺子的出牌次数+出顺子的数量 是否大于答案,即更新答案。
然后枚举三种顺子:
单,双和三顺。
枚举 顺子起点,顺子长度,判断可行,更新递归。
OK!
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 20
#define MAX 2147483647
using namespace std;
int T,n,x,y,ans,j;
int sum[N];
inline int read()//快读加速
{
int x=0,y=1;char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') {x=x*10+c-'0',c=getchar();}
return x*y;
}
int qwer()//非顺子出牌
{
int x,y,z,zz,ans;
x=y=z=zz=ans=0;
for (int i=1;i<=14;i++)
{
if (sum[i]==1) x++;
if (sum[i]==2) y++;
if (sum[i]==3) z++;
if (sum[i]==4) zz++;
}
while ((y/2)&&(zz))
{
ans++;
y-=2;
zz--;
}
while ((x/2)&&(zz))
{
ans++;
x-=2;
zz--;
}
while (y&&z)
{
ans++;
y--;
z--;
}
while (x&&z)
{
ans++;
x--;
z--;
}
ans+=x+y+z+zz;
return ans;
}
void dfs(int x)//递归顺子
{
if (x>=ans) return;//剪枝
int bz=0;//判断有无牌
for (int i=1;i<=14;i++)
if (sum[i])
{
bz=1;
break;
}
if (!bz)
{
ans=min(ans,x);//更新
return;
}
int t=qwer();//非顺子出牌数
ans=min(ans,t+x);//更新
for (int i=1;i<=11;i++)//三顺子
for (int j=1;j<=12-i;j++)
{
bz=1;
for (int k=i;k<=i+j;k++)
if (sum[k]<3)
{
bz=0;
break;
}
if (bz)
{
for (int k=i;k<=i+j;k++) sum[k]-=3;
dfs(x+1);
for (int k=i;k<=i+j;k++) sum[k]+=3;
}
}
for (int i=1;i<=10;i++)//双顺子
for (int j=2;j<=12-i;j++)
{
bz=1;
for (int k=i;k<=i+j;k++)
if (sum[k]<2)
{
bz=0;
break;
}
if (bz)
{
for (int k=i;k<=i+j;k++) sum[k]-=2;
dfs(x+1);
for (int k=i;k<=i+j;k++) sum[k]+=2;
}
}
for (int i=1;i<=8;i++)//单顺子
for (int j=4;j<=12-i;j++)
{
bz=1;
for (int k=i;k<=i+j;k++)
if (!sum[k])
{
bz=0;
break;
}
if (bz)
{
for (int k=i;k<=i+j;k++) sum[k]--;
dfs(x+1);
for (int k=i;k<=i+j;k++) sum[k]++;
}
}
}
int main()
{
freopen("landlords.in","r",stdin);
freopen("landlords.out","w",stdout);
T=read(),n=read();
while (T--)
{
j++;
ans=MAX;
memset(sum,0,sizeof(sum));
for (int i=1;i<=n;i++)
{
x=read(),y=read();
if (!x) sum[14]++;//处理顺序
else if (x==1) sum[12]++;
else if (x==2) sum[13]++;
else sum[x-2]++;
}
dfs(0);
printf("%d\n",ans);
}
}