题解 | 斗地主-NOIP2015提高组复赛F题
斗地主
https://ac.nowcoder.com/acm/contest/263/F
题目描述
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A 到K 加上大小王的共54 张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 n 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。
现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：
输入描述:
输入第一行包含用空格隔开的 2 个正整数 T, n ，表示手牌的组数以及每组手牌的张数。
接下来 T 组数据，每组数据 n 行，每行一个非负整数对ai,bi，表示一张牌，其中ai表示牌的数码，bi表示牌的花色，中间用空格隔开。特别的，我们用 1 来表示数码 A，11 表示数码 J，12 表示数码 Q，13 表示数码 K；黑桃、红心、梅花、方片分别用 1-4 来表示；小王的表示方法为 0 1，大王的表示方法为 0 2。
输出描述:
输出共 T 行，每行一个整数，表示打光第 i 组手牌的最少次数。
示例1
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
3
共有1 组手牌，包含8 张牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A 以及黑桃A。可以通过打单顺子（方片7，方片8，黑桃9，方片10，黑桃J），单张牌（黑桃5）以及对子牌（黑桃A 以及方片A）在3 次内打光。
备注
对于不同的测试点，我们约定手牌组数T与张数n的规模如下:
所有手牌都是随机生成的
解答
-
NOIP 2015 斗地主的增强版。不仅仅是数据增强了，其实规则也稍有变化，在这
道题里要注意大小王不再算是一对了，不能当做对子用。
-
如果打过牌，可能会想到一些贪心的做法，但是我相信肯定有人见到这道题之前
完全不会打牌（比如我），所以预处理就只好用dp了。
-
设 dp[i][j][k][z][l]dp[i][j][k][z][l] 表示出现过一次的数码有 ii 个，出现过两次的数码有 jj 个，出现过三次的数码有 kk 个，出现过四次的数码有 zz 个,王有 ll 个的最小出牌次数。
-
如果只是按照题目所给的方法进行转移并不能AC，因为还有一种出牌方法叫做
拆牌，所以出现了以下两种新的转移：
# include <cstdio>
# include <iostream>
# include <cstring>
# define R register int
using namespace std;
int T,n,ans;
int a[16];
int dp[25][25][25][25][3];
int num,col,coun[5];
bool id;
void dfs (int x)
{
if(x>=ans) return;
bool f;
int cnt;
for (R k=1;k<=3;++k)
for (R i=1;i<=12;++i)
{
f=true;
if(k==1) cnt=5;
if(k==2) cnt=3;
if(k==3) cnt=2;
while (f&&i+cnt-1<=12)
{
for (R j=1;j<=cnt;++j)
if(a[i+j-1]<k)
{
f=false;
break;
}
if(f==false) continue;
for (R j=1;j<=cnt;++j)
a[i+j-1]-=k;
dfs(x+1);
for (R j=1;j<=cnt;++j)
a[i+j-1]+=k;
cnt++;
}
}
coun[1]=coun[2]=coun[3]=coun[4]=coun[5]=0;
for (int i=1;i<=13;++i)
coun[ a[i] ]++;
coun[5]=a[14];
ans=min(ans,x+dp[ coun[1] ][ coun[2] ][ coun[3] ][ coun[4] ][ coun[5] ]);
}
void init ()
{
int x=100;
memset(dp,0x3f,sizeof(dp));
dp[0][0][0][0][0]=0;
for (int z=0;z<=n;++z)
for (int k=0;k<=n;++k)
for (int i=0;i<=n;++i)
for (int j=0;j<=n;++j)
for (int l=0;l<=2;++l)
{
x=100;
if(i>0) x=min(x,dp[i-1][j][k][z][l]+1);
if(j>0) x=min(x,dp[i][j-1][k][z][l]+1);
if(k>0) x=min(x,dp[i][j][k-1][z][l]+1);
if(z>0) x=min(x,dp[i][j][k][z-1][l]+1);
if(l>0) x=min(x,dp[i][j][k][z][l-1]+1);
if(l>1) x=min(x,dp[i][j][k][z][l-2]+1);
//单权值
if(i>0&&k>0) x=min(x,dp[i-1][j][k-1][z][l]+1);
if(l>0&&k>0) x=min(x,dp[i][j][k-1][z][l-1]+1);
//三带一
if(j>0&&k>0) x=min(x,dp[i][j-1][k-1][z][l]+1);
//三带二
if(i>1&&z>0) x=min(x,dp[i-2][j][k][z-1][l]+1);
if(i>0&&z>0&&l>0) x=min(x,dp[i-1][j][k][z-1][l-1]+1);
if(z>0&&l>1) x=min(x,dp[i][j][k][z-1][l-2]+1);
if(j>0&&z>0) x=min(x,dp[i][j-1][k][z-1][l]+1);
if(j>1&&z>0) x=min(x,dp[i][j-2][k][z-1][l]+1);
if(z>1) x=min(x,dp[i][j][k][z-2][l]+1);
//四带二
if(z>0) x=min(x,dp[i+1][j][k+1][z-1][l]);
if(k>0) x=min(x,dp[i+1][j+1][k-1][z][l]);
dp[i][j][k][z][l]=min(dp[i][j][k][z][l],x);
}
}
int main()
{
scanf("%d%d",&T,&n);
init();
while (T--)
{
memset(a,0,sizeof(a));
ans=n;
for (int i=1;i<=n;++i)
{
scanf("%d%d",&num,&col);
if(num==0)
{
a[14]++;
continue;
}
if(num>=3) a[num-2]++;
if(num==1) a[12]++;
if(num==2) a[13]++;
}
dfs(0);
printf("%d\n",ans);
}
return 0;
} 
查看7道真题和解析
