[NOIP2015] 斗地主

发表于 | 分类于

题目

传送门

INPUT

第一行包含用空格隔开的2个正整数Tn，表示手牌的组数以及每组手牌的张数。
接下来T组数据，每组数据n行，每行一个非负整数对aibi表示一张牌，其中ai示牌的数码，bi表示牌的花色，中间用空格隔开。特别的，我们用1来表示数码A，11表示数码J，12表示数码Q，13表示数码K；黑桃、红心、梅花、方片分别用1-4来表示；小王的表示方法为01，大王的表示方法为02
。

OUTPUT

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

SAMPLE

INPUT1

1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

OUTPUT1

3

INPUT2

1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2

OUTPUT2

6

解题报告

考试时光顾着T3了，看到它时间根本不够= =，拿了小数据特判分走人= =
显然是个暴搜模拟。
首先，显然花色没用，大王小王也可以看做一样的牌，而且，出牌顺序显然没有影响。
那么剩下的就很简单了，我们先出牌多的（正确性显然，因为这样答案一开始就不会很大，然后你可以用当前答案剪枝，因为已经不比当前答案优的解不可能推出最优解，这样，你可以利用较优的解减掉许多劣解，从而优化），并且，显然顺子一般来说要比带牌要优，那么剩下的就很简单了，注意一些出牌规则，不要像某些不会斗地主的小兄弟 （hww：喵喵喵？） 一样= =
要注意的是，顺子不一定越长越好，比如考虑这样一副牌：

3 4 5 6 7 8 9 9 10 10 J J

若是以越长越优的话，你会做出先打出顺子3~J，再单打9、10、J的决定，但显然打3~8的顺子加9~J的连对更优一些，所以我们在枚举顺子时，需要枚举所有可能的长度。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
    return sum;
}
int size[30];
int n,ans;
inline int get_val(int x){
    if(x==1)
        return 12;
    if(x==2)
        return 13;
    if(x==0)
        return 14;
    return x-2;
}
inline int doit(){
    int tmp(0);
    int tp[6]={0};
    for(int i=1;i<=14;i++)
        tp[size[i]]++;
    while(tp[4]&&tp[2]>=2)
        tmp++,tp[4]--,tp[2]-=2;//四带俩对
    while(tp[4]&&tp[1]>=2)
        tmp++,tp[4]--,tp[1]-=2;//四带俩单
    while(tp[3]&&tp[2]>=1)
        tmp++,tp[3]--,tp[2]--;//三带二
    while(tp[3]&&tp[1]>=1)
        tmp++,tp[3]--,tp[1]--;//三带一
    tmp+=tp[1]+tp[2]+tp[3]+tp[4];
    return tmp;
}
inline int my_min(int a,int b){
    return a<b?a:b;
}
inline void dfs(int cnt){
    if(cnt>ans)
        return;
    int x(doit());
    ans=my_min(ans,cnt+x);
    for(int i=1;i<=11;i++){//三顺子
        int j;
        for(j=i;size[j]>=3&&j<=12;j++);
        if(j-i<2)
            continue;
        for(int k=j;k-i>=2;k--){
            for(int l=i;l<k;l++)
                size[l]-=3;
            dfs(cnt+1);
            for(int l=i;l<k;l++)
                size[l]+=3;
        }
    }
    for(int i=1;i<=10;i++){//连对
        int j;
        for(j=i;size[j]>=2&&j<=12;j++);
        if(j-i<3)
            continue;
        for(int k=j;k-i>=3;k--){
            for(int l=i;l<k;l++)
                size[l]-=2;
            dfs(cnt+1);
            for(int l=i;l<k;l++)
                size[l]+=2;
        }
    }
    for(int i=1;i<=8;i++){//顺子
        int j;
        for(j=i;size[j]>=1&&j<=12;j++);
        if(j-i<5)
            continue;
        for(int k=j;k-i>=5;k--){
            for(int l=i;l<k;l++)
                size[l]--;
            dfs(cnt+1);
            for(int l=i;l<k;l++)
                size[l]++;
        }
    }
}
inline int gg(){
//  freopen("landlords.in","r",stdin);
//  freopen("landlords.out","w",stdout);
    int T(read());
    n=read();
    while(T--){
        memset(size,0,sizeof(size));
        for(int i=1;i<=n;i++){
            int x(read()),y(read());
            size[get_val(x)]++;
        }
        ans=doit();
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}
int K(gg());
int main(){;}

这一顿暴搜= =