构造算法和动态规划
构造算法和动态规划
在我们用DP计数的时候，经常会遇到要求统计不同结果的DP，由于统计的是结果，因此两个不相交的中间状态最终可能会导出相同的结果。这就会导致一个重复统计的问题，有些结果我们统计了多次。
这里讲一下这类问题的通用思路。我们设计一套构造型算法f:V→T，我们可以将指导构造型算法的命令序列（f的入参）视作一个向量v∈V，向量的第i个维度的值vi对应构造型算法的第i步操作，而f(v)就是构造型算法的输出了，其对应一个结果集合（注意是结果集合而不是一个结果）。对于每个可能的结果r，构造型算法都要能构造出来，即存在某个向量v，满足r∈f(v)，并且命令向量可以对结果做一个划分，换言之，若v≠u，那么f(v)∩f(u)=∅。
这样的好处就是我们在根据命令向量做DP计算的时候，由于是不同的命令序列，因此可以保证得到的结果也都是不同的。我们需要的就是通过DP统计每个命令序列的结果集合大小，最后将其加总起来就可以了。
计算包含某个子串的所有串
题目1：给定一个长度为n的串s，问存在多少长度为m的串，满足s是它的子序列（即从中删除一些字符后剩下的字符能拼接成s）。这里1≤n≤m≤106，s和构造出来的串中使用的字符集大小为c。
这个问题就是典型的构造型DP问题。可以发现直接统计结果数很容易会重复统计。并且由于求得是子序列而不是子串，因此也不能KMP或AC自动机的数据结构来统计。
下面我们来设计一个构造型算法。对于某个结果，我们设计的构造型算法是这样的。我们构造一个长度在n和m之间的向量v，其中向量的每个元素都是01，且其中正好有n个1，且最后一个数就是1。我们可以这样解读构造过程，一开始我们有一个空的字符串，对于步骤i，记p=1+∑i−1j=1vi，如果vi不是0，则向构造的字符串后插入一个与sp不同的字符，否则向构造的字符串后面插入sp。当所有命令处理完成，就向构造的字符串尾部插入任意字符，直到它的长度达到m。
可以发现每个结果都可以由某个命令向量构造出来，且不同命令向量的产出是没有交集的，且对于长度为k的命令序列恰好对应(c−1)k−ncm−k个可能的结果。以公式的形式表达，我们要统计的结果数为：
m∑k=n(c−1)k−ncm−k(k−1n−1)上面的结果我们可以通过预处理组合数和指数的方式快速计算出来，时间复杂度为O(m)。
计算网格扩展问题
题目2：假设有一个网格矩阵，初始的时候高度为a，宽度为b，且每个单元格的颜色均为白色。之后我们重复下面操作将矩阵的高变成c，宽变成d。
- 每次操作你可以在网格矩阵的上面加上一行，或右边加上一列，新加的行列覆盖的白色单元格中需要选取一个染成黑色
要求计算有多少不同的结果。其中1≤a≤c≤3000,1≤b≤d≤3000。
一道atcoder的题目。
这个问题也可以用构造型DP来解决。我们考虑命令序列，我们的命令序列是一个长度恰好为n=c+d−a−b的01向量v。下面我们考虑如何通过命令向量构造结果集合：一开始的网格是a行b列的，考虑vi，如果vi=0，则表示向网格的右边加上一列，这里特殊判断如果vi−1=1，则染色的为新列的最高的单元格，否则任意染色。否则如果vi=1，则向上增加一行。
我们考虑将结果翻译回命令向量，假设现在我们已经翻译了一部分，且已经构造了高度为h，宽度为w的矩阵。如果第h+1列加入时染色的块高度t不超过w，我们就向命令向量插入一个0，否则我们就插入t−h个1后再插入一个0。同时我们容易发现从结果到命令向量的构造方式是唯一的。
接下来考虑怎么统计最终的结果。我们发现需要构造一个长度为n的01序列，且其中0出现次数为d−b，1出现的次数为c−a。命令向量v对应的结果集合大小为的计算方式为
∏vi=1(b+i∑j=1[vj=0])⋅∏vi=0∧vi−1=0(a+i∑j=1[vj=1])上面这些统计结果可以通过DP计算，具体做法就是记dp(i,j,k)表示当前构造的01向量中0出现了i次，1出现了j次，且最后一个出现的数为k，上面公式中的前缀乘积。具体的贡献计算非常简单，时间复杂度为O(2(c−a)(d−b))。