浅谈 CSP-S T3 中使用的一类 dp 状态设计

· · 算法·理论

有一些时候，我们会碰到一类 dp，朴素的状态设计是 dp_{i,x,y} 表示处理到第 i 个，现在的状态是 x,y，但是我们发现 x 和 y 的其中一个可以通过 i 确定，于是可以把状态优化成 dp_{i,0/1,t} 表示处理到第 i 个，x/y 可以通过 i 确定，另一个的值是 t。

例子

abc376_f

这是我第一次接触到这一思路，是在 CSP 集训时。

我们发现进行了操作后，就可以确定其中一只手的位置一定在操作指定的位置，于是可以设 dp_{i,j} 表示进行到第 i 次操作，另一只手放在 j 处的最小代价，于是可以 O(n) 分类讨论转移。

CSP-S 2024 T3

刚刚好碰到了集训时的思路，所以赛场上直接切掉了。

我们发现，由于一个格子的颜色不是红就是蓝，所以说如果这一个与上一个填同样的颜色，那么其 ⌈最靠近的同色⌋ 一定是 i - 1，于是可以设计状态 dp_{i,0/1,p} 表示考虑到第 i 个，上一个填的是红/蓝，最靠近的异色为 t 的最大权值。然后先把暴力的 O(n) 转移写出来，发现每次转移只有全局加和单点修改两个操作，可以用线段树优化，于是 O(n\log n) 的做完了，实际上好像可以优化到 O(1) 转移，但是赛时懒得写。

后记

也不是太难的状态设计，即使以前没看过这种方法稍微想一下也能想出来，但是我想出这一思路的时候就感觉很巧妙，于是就写了下来。

最后庆祝一下集训时做到了同样思路的题目，最后 CSP-S 300 分完美收场。