构造算法和动态规划

Published: by Creative Commons Licence

  • Tags:

构造算法和动态规划

在我们用DP计数的时候,经常会遇到要求统计不同结果的DP,由于统计的是结果,因此两个不相交的中间状态最终可能会导出相同的结果。这就会导致一个重复统计的问题,有些结果我们统计了多次。

这里讲一下这类问题的通用思路。我们设计一套构造型算法$f:V\rightarrow T$,我们可以将指导构造型算法的命令序列($f$的入参)视作一个向量$v\in V$,向量的第$i$个维度的值$v_i$对应构造型算法的第$i$步操作,而$f(v)$就是构造型算法的输出了,其对应一个结果集合(注意是结果集合而不是一个结果)。对于每个可能的结果$r$,构造型算法都要能构造出来,即存在某个向量$v$,满足$r\in f(v)$,并且命令向量可以对结果做一个划分,换言之,若$v\neq u$,那么$f(v)\cap f(u)=\emptyset$。

这样的好处就是我们在根据命令向量做DP计算的时候,由于是不同的命令序列,因此可以保证得到的结果也都是不同的。我们需要的就是通过DP统计每个命令序列的结果集合大小,最后将其加总起来就可以了。

计算包含某个子串的所有串

题目1:给定一个长度为$n$的串$s$,问存在多少长度为$m$的串,满足$s$是它的子序列(即从中删除一些字符后剩下的字符能拼接成$s$)。这里$1\leq n\leq m\leq 10^6$,$s$和构造出来的串中使用的字符集大小为$c$

这个问题就是典型的构造型DP问题。可以发现直接统计结果数很容易会重复统计。并且由于求得是子序列而不是子串,因此也不能KMP或AC自动机的数据结构来统计。

下面我们来设计一个构造型算法。对于某个结果,我们设计的构造型算法是这样的。我们构造一个长度在$n$和$m$之间的向量$v$,其中向量的每个元素都是01,且其中正好有$n$个1,且最后一个数就是$1$。我们可以这样解读构造过程,一开始我们有一个空的字符串,对于步骤$i$,记$p=1+\sum_{j=1}^{i-1}v_i$,如果$v_i$不是0,则向构造的字符串后插入一个与$s_p$不同的字符,否则向构造的字符串后面插入$s_p$。当所有命令处理完成,就向构造的字符串尾部插入任意字符,直到它的长度达到$m$。

可以发现每个结果都可以由某个命令向量构造出来,且不同命令向量的产出是没有交集的,且对于长度为$k$的命令序列恰好对应$(c-1)^{k-n}c^{m-k}$个可能的结果。以公式的形式表达,我们要统计的结果数为:

上面的结果我们可以通过预处理组合数和指数的方式快速计算出来,时间复杂度为$O(m)$。

计算网格扩展问题

题目2:假设有一个网格矩阵,初始的时候高度为$a$,宽度为$b$,且每个单元格的颜色均为白色。之后我们重复下面操作将矩阵的高变成$c$,宽变成$d$。

  • 每次操作你可以在网格矩阵的上面加上一行,或右边加上一列,新加的行列覆盖的白色单元格中需要选取一个染成黑色

要求计算有多少不同的结果。其中$1\leq a\leq c\leq 3000,1\leq b\leq d\leq 3000$。

一道atcoder的题目

这个问题也可以用构造型DP来解决。我们考虑命令序列,我们的命令序列是一个长度恰好为$n=c+d-a-b$的01向量$v$。下面我们考虑如何通过命令向量构造结果集合:一开始的网格是$a$行$b$列的,考虑$v_i$,如果$v_i=0$,则表示向网格的右边加上一列,这里特殊判断如果$v_{i-1}=1$,则染色的为新列的最高的单元格,否则任意染色。否则如果$v_i=1$,则向上增加一行。

我们考虑将结果翻译回命令向量,假设现在我们已经翻译了一部分,且已经构造了高度为$h$,宽度为$w$的矩阵。如果第$h+1$列加入时染色的块高度$t$不超过$w$,我们就向命令向量插入一个$0$,否则我们就插入$t-h$个$1$后再插入一个$0$。同时我们容易发现从结果到命令向量的构造方式是唯一的。

接下来考虑怎么统计最终的结果。我们发现需要构造一个长度为$n$的01序列,且其中$0$出现次数为$d-b$,$1$出现的次数为$c-a$。命令向量$v$对应的结果集合大小为的计算方式为

上面这些统计结果可以通过DP计算,具体做法就是记$dp(i,j,k)$表示当前构造的01向量中$0$出现了$i$次,$1$出现了$j$次,且最后一个出现的数为$k$,上面公式中的前缀乘积。具体的贡献计算非常简单,时间复杂度为$O(2(c-a)(d-b))$。