[ABC176F] Brave CHAIN
Problem
hhoppitree 有 \(3n\) 张卡片,其中每张卡片上都写着 \(1\sim n\) 中的一个数,他会重复以下操作 \(n-1\) 次:
- 将最左侧的 \(5\) 张牌任意排列,排列后,删去最左侧的 \(3\) 张牌,如果这三张牌上写着同样的数,hhoppitree 可以获得 \(1\) 分。
最后,如果剩余的 \(3\) 张牌上的数字一样,那么他还可以额外得到 \(1\) 分。
现在,hhoppitree 想要知道,他得到的分数最高是多少。
\(1 \le N \le 2000\),\(1 \le A_{i} \le N\)。
Solution
有一个显然的 \(O(n^3)\) DP,记 \(f_{i, x, y}\) 表示进行了 \(i\) 次操作,剩余序列的左起第一个元素为 \(x\)、第二个元素为 \(y\) 的最大分数。之所以能这样记是因为第 \(i\) 次操作后被影响的是一段 确定 的前缀,即每次操作会影响到 \(3\) 个 确定 的元素,因此只需记录由之前操作剩下的 \(2\) 个元素即可知道当前操作需要执行的 \(5\) 个元素是什么。
由于枚举状态的时间复杂度就达到了 \(O(n^3)\),因此我们不能枚举所有状态。由于 \(f_{i, x, y}\) 对于 \((x, y)\) 关于 \(i\) 单调不降,因此可以考虑采取滚动数组转移,转移时只需枚举需要被更新的状态。
考虑给这个 DP 加上一些策略来优化它,比如这个贪心策略:如果当前操作的牌中存在三张相同数字的牌,那么直接打出计入分数。还是容易猜到的。
我们需要一个把策略套进 DP 转移中的方式。由于我们已经知道了每次操作中的其中 \(3\) 个数,我们可以根据这三个数的值去辅助 DP 转移,换句话说,我们可以用这三个确定的元素去 限制被更新的 DP 状态在一个可以接受的枚举范围内。
下面开始转移。
考虑使用 “满三加一” 的策略:
-
若三个数相同:\(f_{i, x, y} \xleftarrow{\max} f_{i - 1, x, y} + 1\)。由于不能枚举所有状态,因此这里可以将 \(+1\) 直接计入最终的答案,而 \(f_{i, x, y}\) 保持不变。
注意:此时需要立即下一步操作,因为这里视作强行将这三张牌打出,不能进行其它操作。
-
若两个数相同,记 \(p\) 为相同的数,\(q\) 为另一个,则:\(f_{i, x, q} / f_{i, q, x} \xleftarrow{\max} \max(f_{i - 1, p, x} + f_{i - 1, x, p}) + 1\)。枚举 \(x\),更新 \(O(n)\)。
-
记这三个数分别为 \(p, q, r\),则:\(f_{i, q, r} / f_{i, r, q} \xleftarrow{\max} f_{i - 1, p, p} + 1\),对 \(q, r\) 也同理更新,\(O(1)\)。
注意:该更新对存在两个数相同的情况也要进行!!!(问题在于对单独的那一个数进行处理)
考虑重排对 DP 值的影响。记三个数为 \(p, q, r\)。
- 把之前剩下的两个数全部打出,则:\(f_{i, p, q} / f_{i, q, p} / f_{i, p, r} / f_{i, r, p} / f_{i, q, r} / f_{i, r, q} \xleftarrow{\max} \max\limits_{1 \le x, y \le n} (f_{i - 1, x, y}, f_{i - 1, y, x})\)。由于 \(\max\) 值可以随更新时动态维护,因此不用枚举 \(x, y\),仍然是 \(O(1)\) 更新。
- 在剩下的两个数中保留一个,则:\(f_{i, x, p} / f_{i, p, x} / f_{i, x, q} / f_{i, q, x} / f_{i, x, r} / f_{i, r, x} \xleftarrow{\max} \max\limits_{1 \le y \le n}(f_{i - 1, x, y}, f_{i - 1, y, x})\)。同理,对每个 \(x\) 实时维护 \(\max\) 值,实现 \(O(n)\) 更新。
- 将新来的三个数 \(p, q, r\) 全部打出,但这种情况已经被 “满三加一” 的讨论中考虑过了,因此避开了 \(O(n^2)\) 更新。
实现上,可以用 vector 存哪些状态在当轮被更新。
于是总时间复杂度为 \(O(n^2)\),令人感动。调得令人感动。code ABC176F
标签:Brave,CHAIN,max,更新,ABC176F,枚举,le,DP From: https://www.cnblogs.com/Schucking-Sattin/p/17784826.html