[ABC176F] Brave CHAIN

题意

给你 \(3n\) 个数字。每次你可以选取前 \(5\) 个数字，拿走里面任意三个数字，剩下两个，如果拿走的 \(3\) 个数字相等，得分 \(+1\)。问最大得分是多少。

思路

首先我们想尝试贪心。然而不好贪心，因为你不知道前面会给你留下哪两张牌，留下的方案数很多。

题目可以看做每次有三个新数字，和前面两个留下的数字进行操作，它们中留下两个。

此时可以考虑 DP。由前面思考或者部分分提示可以设出 \(dp_{i,x,y}\) 表示考虑到第 \(i\) 组数字（\(3\) 个为一组），留下 \(x,y\) 的最大分数。

于是我们要枚举前面留下哪两个数字，五个数字中留下哪两个数字，状态是 \(O(nV^2)\)，转移考虑一下留下哪两个数字，是常数复杂度，总共 \(O(nv^2)\)。

考虑如何优化。

首先枚举 \(i\) 是必须的，不过空间上可以把这一维滚掉。状态感觉都很有用。

考虑优化转移。分为得分和不得分两种情况考虑，这样代码好写一些吧。设新的三个数字为 \(a,b,c\)。若 \(a=b=c\)，我们直接删除这三个数字得分 \(+1\)，且这样是一定不劣的。反正它们迟早都要删掉，就不必留到后面了。因此这种情况全局 \(+1\)，可以维护一个 \(tag\)。虽然存在不得分的更新方式，但是根据贪心，我们最后的最大得分方案中一定没有把这三个新数留下的情况，这是不优的，因此这种情况不用考虑不得分的转移。

若 \(a,b,c\) 有两个相等，设 \(a=b\)。可以在前面找一个 \(x=a=b,y\in[1,n]\)，进行转移，剩下的牌就是 \(c,y\)，得分 \(+1\)。也可以在前面找 \(x=y=c\)，剩下 \(a,b\)，得分 \(+1\)。

若 \(a,b,c\) 互不相同，可以在前面找 \(x=y=a \ or \ b \ or \ c\)，这里假设选择了 \(a\)。那么剩下的是 \(b,c\)，得分 \(+1\)。

以上转移都是 \(O(n)\) 或 \(O(1)\) 的。下面讨论不得分的情况。

为了方便，不得分的情况可以不用考虑 \(a,b,c\) 相等的情况。虽然这样可能会把得分的情况算入不得分，但由于我们的 \(dp\) 值是取 \(\max\)，所以没有关系。

若新数留下两个假设是 \(a,b\)，那么剩下状态是 \(a,b\)，得分不变。得分等于 \(x,y\) 任取的最大值，可以在上一层 \(dp\) 顺便维护，时间复杂度是 \(O(1)\) 的。

若剩下 \(a,x\)，则剩下状态为 \(a,x\)，我们必须枚举 \(x\)，毕竟它是目前一层的状态。然后对所有可能的 \(y\in[1,n]\) 取最大值，这个也可以在上一层 DP 的时候顺便维护。时间复杂度 \(O(n)\)。

若剩下 \(x,y\)，则我们要枚举所有 \(x,y\)，因为这是状态。但是你发现上面所有的转移都最多只有 \(O(n)\)，而且这个转移极为美丽，它是由 \(x,y\to x,y\) 的。一个小技巧是把上面的转移用临时数组存下来，只有 \(O(n)\) 个，做完上面转移后直接把数组盖到原 DP 数组上，这样我们就不用 copy 一遍 \(n^2\) 的 DP 数组了。

总时间复杂度 \(O(n^2)\)。