DP进阶

· · 个人记录

字典序最小方案

处理方法 1 倒序 DP：

倒着 DP， 原先倒着推方案时最先保证的是最后一位的字典序最小，倒过来就是首先保证第一位的字典序最小。

Eg. 最短包含串（字典序最小版）

给定字符串 a 和 b，求最短的字符串 s，使得 a 与 b 均为 s 的子序列。

仅求长度太简单了，所以你要找到所有满足条件的 s 中字典序最小的。

先考虑仅求长度；

dp_{i,j}表示 a 前 i 个字符与 b 前 j 个字符的最短包含串, 边界条件({\color{red}最大或最小}) : dp_{i,0} = i, dp_{0,j} = j dp_{i,j} =\begin{cases} & a_i \ne b_j & dp_{i,j} = dp_{i - 1,j - 1} + 1\\ & a_i = b_j & dp_{i, j} = \min(dp_{i - 1,j}, dp_{i, j - 1}) + 1 \end{cases}

再考虑求任意方案；

\large 从 dp_{n,m}开始，考虑 dp_{n,m} 从何处转移，选择转移中的可行的字符，即可求出一种方案, 在这个过程中，可以再 dp_{i,j} 从 dp_{i - 1,j} 与 dp_{i, j - 1}均可转移过来时会出现不同情况，这时候选择字典序最小的那一种即可将这一位的字典序保证最小。

由于只能保证从后往前字典序最小，遂倒序 DP 以保证从前往后字典序最小。

处理方法 2 字符枚举：

从小到大枚举所有字符，通过 DP 得出的信息判断该字符是否可以放在某个位置，已达到字典序最小的目的。

计数问题

算重的解决方案：

  1. 容斥

    Eg. 最长公共子序列计数

    dp_{i,j} =\begin{cases} & a_i \ne b_j & dp_{i,j} = dp_{i - 1,j - 1}\\ & a_i = b_j & dp_{i, j} = dp_{i - 1,j}[f_{i - 1, j} = f_{i,j}] + (dp_{i, j - 1}[f_{i, j} = f_{i, j - 1}]) {\color{red}{- (dp_{i - 1, j - 1}[f_{i,j} = f_{i - 1, j - 1}])}}两者都不在公共子序列的情况 \end{cases}

  2. 替换状态为不重不漏