dp of dp

EternalAlexander · 2020-05-16 18:06:51 · 个人记录

最近有一些学到的东西，想写几个这种专题随笔记录一下，也可以给有兴趣的选手做一个参考。

大概是会放某一种套路的几个例题吧。

反正就是打算先写一个试试。至于今天为什么选 dp of dp 这个主题，因为这三道题都是我独立做出来的，写这个可能体会深一点，也会比较有成就感？

个人水平有限，涉及内容大概只有普及组难度，并且难免有一些错误吧，可以选择性观看。

一

顾名思义，dp of dp 是一种在 dp 状态里记录另一个 dp （也不一定是 dp，可能是贪心算法）的状态，从而进行计数的方式。

可能这么说不是很清楚，我们先看一道例题：

对于一个数，你可以进行任意次操作，每次操作可以删去数字相同的连续一段，例如你可以把 1122331 变成 22331，11331，11221 或者 112233。当然，如果整个数都是连续的一段，那么我们可以将它变成 0。

记把 i 变成 0 的最少操作次数是 f(i)，给出 k,l,r，求 l 到 r 内的数有多少满足 f(i) = k。 l,r \leq 10^{18}。

（这个题时间久远，而且不在任何我已知的 oj 上，并且题面是凭记忆写的，不一定完全准确）

第一眼并不知道怎么入手。首先想一想，怎么求这个 f(i)？

一个显然的做法是从大到小（其实任意顺序都是对的)处理每种数字，将这种数字的连续段删掉。比如 1122331 \rightarrow 11221 \rightarrow 111 \rightarrow 0。

我们简化一下这个过程，维护一个单调栈，从左往右扫，把遇到的数字入栈时，将栈中大于自己的数都弹掉，并且使 ans+1，然后如果等于自己就合并起来（就是删掉当前插入的这个），小于则插入。

然后怎么计数呢？l,r \leq 10^{18}，这是写在题面上的让你数位 dp。我们考虑把单调栈的状态压进 dp 的状态。设 f_{i,j,S,0/1} 表示考虑到第 i 位，前面已经消耗的代价为 j，当前单调栈中的元素为 S（这里 S 是一个集合，容易发现我们只要知道单调栈中有哪些数字就可以还原单调栈了），并且已经/没有达到数位限制的方案数。这样就可以按套路数位 dp 了。

后来讲题的老师说，这玩意有一个好听的名字，较做 dp of dp。

二

写这个的直接原因是随机跳题跳到了 p1758 。

upd：经 srf 神犇指教，这个题有更容易的理解方式。

首先 a^2 非常地难以统计，我们考虑把这个平方换掉。答案为：对于所有操作序列得到的结果，得到它的操作序列的方案数之和。

这里的 操作序列 是一个长为 n+m，由 A 和 B 组成的序列，其中 A 表示第 i 步中取了上管道的球，B 表示取下管道的球。

首先考虑对于一个操作序列，如何统计有多少种操作序列能得到和它一样的结果。

先把按照这个操作序列操作得到的串写出来，然后是一个普及组dp：f_{i,j,k} 表示前 i 位，上/下管道的球分别取到了 j,k 的方案数。注意到 k 可以由 i 和 j 算出来，我们只需要记录两维。

然后，我们要计算所有操作序列的答案之和。发现了吗，这就是个 dp of dp！