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);
}