「Codeforces 1110D」Jongmah

发表于 | | 阅读次数:
字数统计: 568 字

Description

题目链接：Codeforces 1110D

你在玩一个叫做 Jongmah 的游戏，你手上有 $n$ 个麻将，每个麻将上有一个在 $1$ 到 $m$ 范围内的整数 $a_i$。

为了赢得游戏，你需要将这些麻将排列成一些三元组，每个三元组中的元素是相同的或者连续的。如 $7,7,7$ 和 $12,13,14$ 都是合法的。你只能使用手中的麻将，并且每个麻将只能使用一次。

请求出你最多可以形成多少个三元组。

数据范围：$1\le n,m\le 10^6$，$1\le a_i\le m$

Solution

首先我们必须注意到：相同的 $3​$ 个 $[x,x+1,x+2]​$ 三元组，可以变成 $[x,x,x]​$，$[x+1,x+1,x+1]​$，$[x+2,x+2,x+2]​$ 这样 $3​$ 个三元组，而并没有改变三元组的数量。这样一来，我们就可以假设，对于每个 $x​$，形如 $[x,x+1,x+2]​$ 的三元组最多只有 $2​$ 个！

我们可以直接定义 $\text{DP}$ 状态：$f_{x,i,j}$ 表示考虑到前 $x$ 种数字，有 $i$ 个 $[x-1,x,x+1]$，$j$ 个 $[x,x+1,x+2]$，我们枚举有 $k$ 个 $[x+1,x+2,x+3]$，状态转移方程如下（我们记 $cnt_i$ 表示数字 $i$ 的数量）：

其中 $i,j,k$ 分别表示：有 $i$ 个 $[x-2,x-1,x]$，有 $j$ 个 $[x-1,x,x+1]$，有 $k$ 个 $[x,x+1,x+2]$，那么肯定有 $i+j+k$ 个数字 $x​$，得到约束条件和贡献后直接转移。

时间复杂度：$O(3^3\cdot m)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=1e6+5,M=3;
int n,m,a[N],f[M][M],g[M][M];

int main() {
    scanf("%d%d",&n,&m);
    for(int x,i=1;i<=n;++i) scanf("%d",&x),++a[x];
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;
    for(int p=1;p<=m;++p) {
        memcpy(g,f,sizeof(f));
        memset(f,-0x3f,sizeof(f));
        for(int i=0;i<3;++i) for(int j=0;j<3;++j) for(int k=0;k<3;++k) {
            if(i+j+k<=a[p]) f[j][k]=std::max(f[j][k],g[i][j]+(a[p]-i-j-k)/3+k);
        }
    }
    printf("%d\n",f[0][0]);
    return 0;
}
0%