LibreOJ 3084.「GXOI / GZOI2019」宝牌一大堆

太上头了……
等会得去打一局雀魂挫败一下我写麻将题的兴趣(

看到麻将题就考虑 DP,设 \(f_{i,j,0/1,x,y,z}\) 表示考虑了前 \(i\) 种牌,做了 \(j\) 个面子,无 / 有雀头,第 \(i-2\) 种牌用了 \(x\) 张,第 \(i-1\) 种牌用了 \(y\) 张,第 \(i\) 种牌用了 \(z\) 张时的最高分数。
但是注意到这样子转移的时候需要除以组合数或乘组合数,稍微有点麻烦;又注意到这些乘除的发生只是因为第 \(i-2,i-1,i\) 种牌的转移。
所以,可以把状态表示的东西改成:该情况下前 \(i-3\) 种牌的最高分数。

然后注意到实际上杠子是没用的……刻子显然是比杠子优的……
以及七对子直接贪心,国士无双直接枚举那个出现两次的牌。

(参考了 lydrainbowcat 大佬的 std)

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 34;
const int M = 13;
const int shuntsu[] = {0,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0};
const int yaochu[M] = {1,9,10,18,19,27,28,29,30,31,32,33,34};
const int C[5][5] =
{
{1,0,0,0,0},
{1,1,0,0,0},
{1,2,1,0,0},
{1,3,3,1,0},
{1,4,6,4,1}
};
int T,n = N,m = M,a[N + 5],dora[N + 5];
int c[N + 5];
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret *= a),a *= a;
return ret;
}
long long f[N + 5][5][2][5][5][5],ans;
inline int id(const char *s)
{
return
s[0] == 'E' ? 28 :
s[0] == 'S' ? 29 :
s[0] == 'W' ? 30 :
s[0] == 'N' ? 31 :
s[0] == 'Z' ? 32 :
s[0] == 'B' ? 33 :
s[0] == 'F' ? 34 :
s[1] == 'm' ? s[0] - '0' :
s[1] == 'p' ? s[0] - '0' + 9 :
s[1] == 's' ? s[0] - '0' + 18 :
0;
}
inline void calc()
{
memset(f,0,sizeof f),f[1][0][0][0][0][0] = 1;
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= 4;++j)
for(register int k = 0;k < 2;++k)
for(register int x = 0;x <= (i > 2 ? a[i - 2] : 0);++x)
for(register int y = 0;y <= (i > 1 ? a[i - 1] : 0);++y)
for(register int z = 0;z <= a[i];++z)
if(f[i][j][k][x][y][z])
i < n && (f[i + 1][j][k][y][z][0] = max(f[i + 1][j][k][y][z][0],f[i][j][k][x][y][z] * (i > 2 ? C[a[i - 2]][x] * fpow(dora[i - 2],x) : 1))),
j < 4 && z + 3 <= a[i] && (f[i][j + 1][k][x][y][z + 3] = max(f[i][j + 1][k][x][y][z + 3],f[i][j][k][x][y][z])),
j < 4 && shuntsu[i] && x < a[i - 2] && y < a[i - 1] && z < a[i] && (f[i][j + 1][k][x + 1][y + 1][z + 1] = max(f[i][j + 1][k][x + 1][y + 1][z + 1],f[i][j][k][x][y][z])),
k < 1 && z + 2 <= a[i] && (f[i][j][k + 1][x][y][z + 2] = max(f[i][j + 1][k + 1][x][y][z + 2],f[i][j][k][x][y][z]));
for(register int i = 0;i <= a[n - 2];++i)
for(register int j = 0;j <= a[n - 1];++j)
for(register int k = 0;k <= a[n];++k)
ans = max(ans,f[n][4][1][i][j][k] * C[a[n - 2]][i] * C[a[n - 1]][j] * C[a[n]][k] * fpow(dora[n - 2],i) * fpow(dora[n - 1],j) * fpow(dora[n],k));
}
inline void chitoitsu()
{
long long res = 7;
for(register int i = 1;i <= n;++i)
c[i] = C[a[i]][2] * fpow(dora[i],2);
sort(c + 1,c + n + 1);
for(register int i = n - 6;i <= n;++i)
res *= c[i];
ans = max(ans,res);
}
inline void kokushimusou()
{
long long res;
for(register int i = 0;i < m;++i)
if(!a[yaochu[i]])
return ;
for(register int i = 0;i < m;++i)
{
if(a[yaochu[i]] > 1)
{
res = C[a[yaochu[i]]][2] * fpow(dora[yaochu[i]],2) * 13;
for(register int j = 0;j < m;++j)
(i ^ j) && (res *= a[yaochu[j]] * dora[yaochu[j]]);
ans = max(ans,res);
}
}
}
int main()
{
scanf("%d",&T);
for(char s[5];T;--T)
{
ans = 0;
for(register int i = 1;i <= n;++i)
a[i] = 4,dora[i] = 1;
for(;~scanf("%s",s) && (s[0] ^ '0');--a[id(s)]);
for(;~scanf("%s",s) && (s[0] ^ '0');dora[id(s)] = 2);
calc(),chitoitsu(),kokushimusou();
printf("%lld\n",ans);
}
}