Codeforces 1110D.Jongmah

(是的又是个麻将题)

首先我们把牌面上为 \(x\) 的牌称为第 \(x\) 种牌。
考虑 DP,设 \(f_{i,j,k}\) 表示前 \(i\) 种牌,除了面子以外留出了 \(j\)\((i-1,i)\)\(k\)\(i\)
注意到 \(0 \le j,k < 3\),否则可以算成刻子。
则转移时枚举预留多少张牌即可,剩下的牌都贪心地组成面子。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6;
int n,m,a[N + 5];
int f[N + 5][3][3],ans = -0x3f3f3f3f;
int main()
{
scanf("%d%d",&n,&m);
int x;
for(register int i = 1;i <= n;++i)
scanf("%d",&x),++a[x];
memset(f,-0x3f,sizeof f),f[0][0][0] = 0;
for(register int i = 1;i <= m;++i)
for(register int j = 0;j < 3;++j)
for(register int k = 0;k < 3;++k)
for(register int l = 0;l < 3 && j + k + l <= a[i];++l)
f[i][k][l] = max(f[i][k][l],f[i - 1][j][k] + j + (a[i] - j - k - l) / 3);
for(register int i = 0;i < 3;++i)
for(register int j = 0;j < 3;++j)
ans = max(ans,f[m][i][j]);
printf("%d\n",ans);
}