BZOJ4325【NOIp2015】斗地主 <搜索+贪心>

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

斗地主

Time Limit: 30Sec30 Sec
Memory Limit: 1024MB1024 MB

Description

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的AA到KK加上大小王的共5454张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由nn张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

![](http://www.lydsy.com/JudgeOnline/upload/201511/11.PNG)

Input

第一行包含用空格隔开的22个正整数T,NT,N，表示手牌的组数以及每组手牌的张数。
接下来TT组数据，每组数据NN行，每行一个非负整数对Ai,BiA_i,B_i，表示一张牌，其中AiA_i表示牌的数码，BiB_i表示牌的花色，中间用空格隔开。特别的，我们用1来表示数码A，1111表示数码JJ，1212表示数码QQ，1313表示数码KK；黑桃、红心、梅花、方片分别用1∼41\sim 4来表示；小王的表示方法为0101，大王的表示方法为0202。

Output

共TT行，每行一个整数，表示打光第TT组手牌的最少次数。

Sample Input

1
2
3
4
5
6
7
8
9
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

Sample Output

1
3

HINT

共有11组手牌，包含88张牌：方片77，方片88，黑桃99，方片1010，黑桃JJ，黑桃55，方片AA以及黑桃AA。可以通过打单顺子（方片77，方片88，黑桃99，方片1010，黑桃JJ），单张牌（黑桃55）以及对子牌（黑桃AA以及方片AA）在33次内打光。
T≤10T\le 10, N≤23N\le 23

UOJUOJ传送门

标签：搜索 贪心

Solution

题面看起来挺吓人，做起来却比较容易，特别是代码复杂度不高（毕竟做了恶心的猪国杀作铺垫）。
发现确定顺子之后，其他所有牌都可以贪心取，从耗费牌数多的往牌数少的取。
用一个DFSDFS作大框架，在DFSDFS到每一层（即每次取一组顺子）的前后用贪心算出当前不再取顺子而直接贪心取的总次数，打擂即可。

Code

（貌似这个代码只能过原数据，加强版因为“有几个相同的王不能组成对子”这一bugbug，我的代码过不了，要加特判）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#define SIZE 14
#define INF 2147483647
using namespace std;
int n, ans, c[SIZE];
void init() {ans = INF;    for (int i = 0; i < SIZE; i++)	c[i] = 0;}
void modify(int l, int r, int x) {for (int i = l; i <= r; i++)    c[i] += x;}
int calc() {
    int c1, c2, c3, c4, ret;	c1 = c2 = c3 = c4 = ret = 0;
    for (int i = 0; i < SIZE; i++)	c1 += (c[i] == 1), c2 += (c[i] == 2), c3 += (c[i] == 3), c4 += (c[i] == 4);
    while (c2 >= 2 && c4 >= 1)	c2 -= 2, c4 -= 1, ret++;	while (c2 >= 1 && c3 >= 1)	c2 -= 1, c3 -= 1, ret++;
    while (c1 >= 2 && c4 >= 1)	c1 -= 2, c4 -= 1, ret++;	while (c2 >= 1 && c4 >= 1)	c2 -= 1, c4 -= 1, ret++;
    while (c1 >= 1 && c3 >= 1)	c1 -= 1, c3 -= 1, ret++;	return ret+c1+c2+c3+c4;
}
void DFS(int stp) {
    int lft = calc();	bool flag = false;
    if (stp > ans)	return;	ans = min(ans, stp+lft);
    for (int l = 2; l+1 < SIZE; l++) {
        int tr = l;	while (c[tr] >= 3 && tr < SIZE)	tr++;
        if (--tr-l+1 < 2)	continue;	flag = true;
        for (int r = tr; r >= l+1; r--)	modify(l, r, -3), DFS(stp+1), modify(l, r, 3);
    }
    for (int l = 2; l+2 < SIZE; l++) {
        int tr = l; while (c[tr] >= 2 && tr < SIZE)	tr++;
        if (--tr-l+1 < 3)	continue;	flag = true;
        for (int r = tr; r >= l+2; r--)	modify(l, r, -2), DFS(stp+1), modify(l, r, 2);
    }
    for (int l = 2; l+4 < SIZE; l++) {
        int tr = l;	while (c[tr] >= 1 && tr < SIZE)	tr++;
        if (--tr-l+1 < 5)	continue;	flag = true;
        for (int r = tr; r >= l+4; r--)	modify(l, r, -1), DFS(stp+1), modify(l, r, 1);
    }
    lft = calc(), ans = min(ans, stp+lft);
}
int main() {
    int T;	scanf("%d%d", &T, &n);
    while (T--) {
        init();
        for (int i = 0, a, b; i < n; i++)	scanf("%d%d", &a, &b), a = a == 1 ? 13 : (a == 0 ? 0 : a-1), c[a]++;
        DFS(0), printf("%d\n", ans);
    }
    return 0;
}