【题解】CF1110D Jongmah

代码很短，但是思路我怎么也想不到的神仙 DP。

题意概述

你在玩一个叫做 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\)

思路分析

首先我们定义第 \(i\) 个顺子表示三个麻将上写着 \(\{i,i+1,i+2\}\) 的三元组，\(i\) 的三连击表示三个麻将上都写着 \(i\) 的三元组，\(cnt_i\) 表示写着 \(i\) 的麻将数。

那么有一个结论是：对于每个 \(i(1 \le i \le m)\)，第 \(i\) 个顺子最多只需要两次。因为 \(3\) 个第 \(i\) 个顺子可以转化为 \(3\) 个三连击（\(i,i+1,i+2\) 的三连击），所以一定存在最优解满足第 \(i\) 个顺子取不超过两次。这是麻将题的常见技巧。

那么我们就可以考虑枚举第 \(i\) 个顺子选了多少次（\(0,1\) 或 \(2\) 次）。

如果直接枚举每个顺子选了多少次，是 \(3^m\) 的复杂度，不能接受。考虑通过 DP 优化。

但是如果直接 DP，发现很难进行状态设计，那么我们可以考虑简化问题。

考虑先解决如下问题：

如果我们并不是可以选择每个顺子，而是只能选择第 \(i\) 个顺子（其中 \(i\bmod 3=1\)），那么如何确定有多少种合法的选择方案。

这个问题的简化之处就在于，第 \(i\) 个的顺子的选择不受任何其它顺子的限制。

那么我们可以直接定义 \(dp_i\) 表示选到了第 \(i\) 个顺子总共有多少种三元组的选择情况。然后枚举选择次数 \(k\)，则对于每个 \(i\)，选择 \(i\) 的三连击的个数是 \(\left \lfloor\dfrac{cnt_i-k}{3}\right\rfloor\)，那么 \(dp_i\) 就可以用 \(dp_{i-3}\) 加上第 \(i\) 个顺子的选择情况再加上 \(i,i-1,i-2\) 的三连击的选择情况而得到，那么有：

\[dp_{i}=\max\limits_{0 \le k \le 2}\{dp_{i-3}+k+\left \lfloor\dfrac{cnt_i-k}{3}\right\rfloor+\left \lfloor\dfrac{cnt_{i-1}-k}{3}\right\rfloor+\left \lfloor\dfrac{cnt_{i-2}-k}{3}\right\rfloor\} \]

这是只能选择第 \(i(i\bmod 3=1)\) 个顺子的情况。

那么对于所有 \(1\le i \le m\) 的每一个 \(i\) 都能选的情况呢？

可以发现这个时候第 \(i\) 个的顺子的选择情况和 \(i\) 的三连击的选择情况，都受到第 \(i-1\) 个顺子的选择情况和第 \(i-2\) 的顺子选择情况的影响，这个时候我们就不能直接定义 \(dp_i\) 表示选到了第 \(i\) 个顺子的方案来解决问题了。我们考虑将第 \(i-1\) 个顺子的选择情况和第 \(i-2\) 个顺子的选择情况加进状态，由于这里第 \(i\) 个顺子的选择情况也会影响到后面第 \(i+1\) 个顺子的选择情况，所以也要把它加进状态，即 \(dp_{i,j,k,t}\) 表示考虑到了第 \(i\) 个顺子，第 \(i\) 个顺子选择了 \(j\) 次，第 \(i-1\) 个顺子选择了 \(k\) 次，第 \(i-2\) 个顺子选了 \(t\) 次的方案数，那么这时候 \(dp_{i,j,k,t}\) 就可以直接由 \(dp_{i-1,k,t,l}\) 其中 \(l\) 是第 \(i-3\) 个顺子的选择情况。

这时候我们发现，第 \(i-3\) 个顺子的选择情况，对第 \(i\) 个顺子的选择情况和 \(i\) 的三连击的选择情况没有影响。同时在 \(dp_{i-1,k,t,l}\) 的状态里已经包含了第 \(i-2\) 个顺子的选择情况，所以我们可以将状态的最后一维删去。那么我们最终确定的 dp 状态就是：\(dp_{i,j,k}\) 表示考虑到了第 \(i\) 个顺子，第 \(i\) 个顺子选择了 \(j\) 次，第 \(i-1\) 个顺子选择了 \(k\) 次的方案数是多少。

那么对于 \(dp_{i,j,k}\)，就可以由 \(dp_{i-1,k,t}\) 转移而来，其中 \(t\) 表示第 \(i-2\) 个顺子选择了 \(t\) 次。然后我们枚举 \(j,k,t\)，那么 \(dp_{i,j,k}\) 就等于 \(dp_{i-1,k,t}\) 加上第 \(i\) 个顺子选择次数 \(j\) 再加上 \(i\) 的三连击的选择次数。

现在问题就转化为，如何在已知 \(j,k,t\) 的情况下，求 \(i\) 的三连击可以选择多少次。

假设 \(j=1,k=1,t=1\)，如图所示：

由该图可知，红色的部分即为三连击的个数，即 \(\left\lfloor\dfrac{cnt_i-j-k-t}{3}\right\rfloor\)。

那么总的转移方程式就为：

\[dp_{i,j,k}=\max\{dp_{i-1,k,t}+j+\left\lfloor\dfrac{cnt_i-j-k-t}{3}\right\rfloor\} \]

时间复杂度 \(O(27n)\)。

代码实现

代码

//CF1110D
//The Way to The Terminal Station…
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
int dp[maxn][3][3],a[maxn],cnt[maxn];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main()
{
	int n,m;
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		cnt[a[i]]++;
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<3;j++)
		{
			for(int k=0;k<3;k++)
			{
				for(int t=0;t<3;t++)
				{
					if(cnt[i]<j+k+t)continue;
					dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][t]+(cnt[i]-j-k-t)/3+j);
				}
			}
		}
	}
	cout<<dp[m][0][0]<<"\n";
	return 0;
}