dp 套 dp扯谈

1.【扯谈概念】

\(dp\) 套 \(dp\) 其实也就是 \(dp\) 。

这里就定义下面两个概念：

内层 \(dp\) 表示的是被套在里面的那个 \(dp\)

外层 \(dp\) 表示的是最外面的那个 \(dp\)

这样可能比较抽象。

举个例子，像这种形式的 \(dp\) 转移：

\[f[i][j]=\max(f[i][j],f[i][j-k]+g[i][k]）
\]

在这里面 \(g[i][k]\) 是不定的，就是我们开始不知道，是我们求出来的，然后我们利用它去进行后面的转移，把它在后面当成一个恒定的 \(val\) 。我们把求解这个 \(g\) 的过程就叫做内层 \(dp\)。

而我们发现 \(f\) 就是我们要求的真正的一个答案状态，然后是把求解这个 \(g\) 的过程包含着的，我们就把求解 \(f\) 的过程叫做外层 \(dp\) 。

而求解这个问题的过程就叫做 \(dp\) 套 \(dp\) 。

本质上说其实 \(dp\) 套 \(dp\) 在我的理解来看就是首先就是将内层的 \(dp\) 结果，作为外层 \(dp\) 进行转移的方法。

如果通俗说就是先算出每一步可能产生的贡献。

然后依托贡献在来进行一次 \(dp\) 。

你单独看着这个概念，你可能似懂非懂的。

因为这个东西确实有点抽象，下面配合例题来进行讲解。

有 \(n\) 块木板，每一块木板长度为 \(m\) ，你可以粉刷 \(t\) 次，每次只能粉刷一块木板上连续的一部分为同一颜色（红色或蓝色），给你一个期望粉刷出的木板的颜色，问你最多能粉刷出多少个与期待相同颜色的格子。

当拿到这个题目的时候，根据传统，它求什么我们就设什么。

我们可以设状态为 \(f[i][j][k]\) 表示刷 \(i\) 次，刷到第 \(j\) 行，第 \(k\) 列的最多正确粉刷数量。

考虑去转移这个方程，发现可以写出这样的状态转移：

\[f[i][j][k]=\sum_{l=0}^{k-1} max(f[i][j][k],f[i-1][j][l]+g[j][l][k])
\]

其中的 \(g[j][l][k]\) 表示的是第 \(j\) 行第 \(l\) 列到第 \(k\) 列的最多粉刷正确数。

注意转移的时候从上一行到下一行的处理。

然后这个方程就没问题了。

分析这么的时间复杂度为 \(O(tnm^3)\)

如果将 \(n\) 与 \(m\) 认为同阶，那么复杂度为 \(O(tn^4)\)

显然不可过的样子，得优化一下。

我们考虑 \(dp\) 的复杂度都来源于哪里？

可能是枚举状态也可能是转移的复杂度。

这个转移的复杂度我们发现是无法有效的优化的（至少我不会）。

然后我们考虑缩小它的状态，我们能发现我们等价于是枚举了每个点的 \(dp\) 情况。

我们试着把它弄为每行的 \(dp\) 情况。

那么状态就变为： \(f[i][j]\) 表示的是第 \(i\) 行刷 \(j\) 次的最大正确粉刷数量。