题目描述
牛牛最近迷上了一种叫斗地主的扑克游戏。
斗地主是一种使用黑桃、红心、梅花、 方片的 A 到 K 加上大小王的共 54 张牌来进行的扑克牌游戏。
在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。
每一局游戏中,一副手牌由 n 张牌组成。
游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。
现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。
请你帮他解决这个问题。
需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
具体规则如原题图:
样例
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
3
算法 dfs
看数据范围就能知道算法,就是写起来生艹,看看大家的代码大多都在百行,于是写了个短点的
大体思路就是先出顺子,之后在剩余的牌里找能排出来的组合,具体细节放注释了(如果有思路更清晰,更简短的代码,欢迎前来讨论)
时间复杂度
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int T, n;
int ans, s[N], c[5];
// ans : 出牌次数
// s[i] : i号牌的张数
// c[i] : 同号牌有i张的个数
int num()
{
int tot = 0; // 剩余的牌中能组成特殊牌组的数量
memset(c, 0, sizeof c);
for (int i = 0; i <= 13; i ++ )
c[s[i]] ++ ;
while (c[4] > 0 && c[2] >= 2) // 四带二 (任意两对牌)
{
c[4] -- ; c[2] -= 2; tot ++ ;
}
while (c[4] > 0 && c[1] >= 2) //还是四带二
{
c[4] -- ; c[1] -= 2; tot ++ ;
}
while (c[4] > 0 && c[2] > 0) // 依然是四带二(毕竟任意两张单牌就行嘛)
{
c[4] -- ; c[2] -- ; tot ++ ;
}
while (c[3] > 0 && c[2] > 0) // 三带二
{
c[3] -- ; c[2] -- ; tot ++ ;
}
while (c[3] > 0 && c[1] > 0) // 三带一
{
c[3] -- ; c[1] -- ; tot ++ ;
}
return tot + c[1] + c[2] + c[3] + c[4]; // 剩余的牌中能出牌的次数
}
void dfs(int x)
{
if (x >= ans) return;
ans = min(ans, x + num());
for (int i = 3; i; i -- ) // 顺子,从大到小枚举
for (int j = 2; j <= 13; j ++ ) // 牌号
{
int p = j;
while (s[p] >= i && p <= 13)
{
p ++ ;
if ((i == 3 && p - j >= 2) || (i == 2 && p - j >= 3) || (i == 1 && p - j >= 5)) // 能组成顺子
{
for (int k = j; k < p; k ++ ) s[k] -= i; // 把能组成顺子的牌去掉
dfs(x + 1); // 顺子数 +1
for (int k = j; k < p; k ++ ) s[k] += i; // 递归结束,把牌再加回来
}
}
}
return;
}
int main()
{
scanf("%d%d", &T, &n);
while (T -- )
{
ans = n; // 最多出牌数(一张一张出)
memset(s, 0, sizeof s);
for (int i = 1; i <= n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
// 下面三行我把牌按0 ~ 13排了下序,A是13,其他除大小王号数都减一
if (a == 1) a = 13;
else if (a > 0) a -- ;
s[a] ++ ;
}
dfs(0); // 从没出过顺子开始递归
printf("%d\n", ans);
}
return 0;
}
三
代
二?已改正