割裂与分步转移

又到了喜闻乐见的社论环节，但这篇可能较为简单了。

抄袭自 dp 多维状态的优化 - chasedeath - 博客园。下面这段话讲的很好，我就搬过来了！

面对一个多维 DP 问题，根据维度之间联系的紧密程度，我们可以选择：

维度之间紧密相关，只能直接枚举；
维度之间完全无关，只是贡献通过某种形式相加，可以割裂为两个 DP 处理；
介于 $1$ , $2$ 之间，不能割裂计算，但是可以将转移过程割裂为若干步来优化。

割裂

题意

给出 $[1,n]$ 的所有子区间的权值，即 $[i,j]$ 权值为 $w(i,j)$ 。称一个区间序列 $[a_1,b_1],[a_2,b_2],\ldots,[a_k,b_k]$ 是合法的当且仅当对于 $i\in[1,k)$ 都有 $a_i<a_{i+1}$ 且 $b_i>b_{i+1}$ 。此时定义其权值为 $\sum\limits_{i=1}^{k-1}w(a_{i-1},a_{i})+w(b_{i},b_{i-1})$ ，求合法区间序列的权值的最大值。

朴素 DP

$dp_{a,b}$ 表示最后一个区间选择 $[a,b]$ 时已有的最大权值， $O(n^4)$ 。

割裂

显然算贡献时无需同时知道 $a,b$ 的配对关系，因为 $a$ 的限制只与 $a$ 的相邻项有关， $b$ 只与 $b$ 的相邻项有关。

我们将 $a$ 与 $b$ 的转移割裂开来，也就是分别选出 $a$ 的递增序列、 $b$ 的递减序列，最后对位拼在一起。那么判断能拼在一起需要二者长度一致，还需要知道 $a$ 的最后一项与 $b$ 的最后一项的大小关系。

那么不妨 $f_{i,j}$ 表示选了长度为 $i$ 、结尾为 $j$ 的 $a$ 的递增序列的最大价值， $g_{i,j}$ 同理。状态数 $O(n^2)$ ，转移 $O(n)$ ，最终合并答案需要 $O(n^2)$ ，总的复杂度是 $O(n^3)$ 。

分步转移

题意

朴素 DP

$dp_{a,b}$ 表示最后一个区间选择 $[a,b]$ 时已有的最大权值， $O(n^4)$ 。

分步转移

由上个题加上了区间的权值，不太容易割裂了，但转移时两维的限制仍然没有必然联系。

技巧是先转移 $a$ 这一维，再转移 $b$ 这一维。具体地，另设 $f_{i,j}$ 表示这个区间右端点为 $j$ 时，如果我下一个区间左端点选 $i$ ，已知贡献的最大值。

$f$ 由 $dp$ 推导：枚举所有可能的下一个左端点， $dp_{a,b}+w(a,c)\to f_{c,b}$ 。
$dp$ 由 $f$ 推导：枚举未选的右端点，容易发现贡献都可以被表示出， $f_{a,b}+w(a,c)+w(c,b)\to dp_{a,c}$ 。

这样转移就只用枚举左右端点中一个，复杂度 $O(n^3)$ 。

一道初赛题

定义函数 $w(x)=\operatorname{popcount}(x)+x$ ，给一个长度为 $n$ 的序列 $a$ ，选其一个子序列 $b$ ，使得 $\sum w(b_i \oplus b_{i+1})$ 最大。 $n \leq 10^5$ , $a_i \leq 2^{16}$ 。

脑洞

将 $a_i$ 看成其前 $8$ 位与后 $8$ 位组成的二元组。磷脂含说这个非常套路，并举出了一个例子，但我不这么觉得。唉！还是见识短浅了。

贡献看似可以割裂，但这俩必须绑起来选，就不那么好做了。那么一样的套路， $f_{i,j}$ 表示我上一个后 $8$ 位是 $j$ ，如果我此数前 $8$ 位填 $i$ ，已知贡献的最大值。转移同理，复杂度变成了 $O(n\sqrt a)$ 。

Extra

相近的思路还出现在：

P7648 [COCI2012-2013#5] MNOGOMET，Sol。
P5289 [十二省联考 2019] 皮配，Sol。