把 DP 过程当作状态进行 DP。DP of DP 一般数据范围不会太大,而且一般是计数题。
DP of DP 的本质是自动机上 DP。 大致上可以写作 \(dp[\dots][S]\) 表示外层 DP 进行到 \(\dots\) 阶段,内层 DP 对应到 \(S\) 阶段。
例一:基因
题意:给出串 \(s\) 和一个数 \(m\)。\(n=|s|\)。求对于 \(i=0\sim n\),有多少串 \(t\) 满足 \(|t|=m\) 且 \(LCS(s,t)=i\)。\(n\le 15,m\le 10^3\)。
假设我们已经知道这是一道 DP 套 DP 的题目。那么对于 DP套DP,最重要的想法就是考虑内层 DP 是怎么进行的?
在这题,内层 DP 是 "最长公共子序列"。平时做 LCS,一般是 \(f[i][j]=\max(f[i-1][j],f[i][j-1],f[i-1][j-1]+[s_i=t_j])\)。
考虑完内层 DP,然后就要考虑怎么把内层 DP 的状态压缩入外层 DP 的状态。
因为 \(t\) 是变化的,所以 DP 时拿一维记录目前考虑到 \(t\) 的第 \(i\) 位了;对应的,考虑拿一维 \(S\) 记录此时 \(f[1\sim n][i]\) 的值。
DP of DP 中,一般数据量较小的那一边作为被压缩的内层 DP。 比如这题,\(n\le 15\),用 \(S\) 记录就只用压缩长度 \(15\) 的数组了。
但是我们面临第二个问题:怎么用 \(S\) 记录此时 \(f[1\sim n][i]\) 的值?总不可能开十五维数组。这个点也是大部分 DP of DP 的难点,怎么压缩内层 DP 的状态?这里需要一些神秘的观察。
观察:当 \(j\) 固定,\(f[x+1][j]-f[x][j]\in \{0,1\}\)。
证明:
按 \(j\) 的大小数学归纳法。\(j=1\) 显然。
若 \(f[x+1][j]=f[x][j]\),立即成立。
若 \(f[x+1][j]=f[x][j-1]+1\),又 \(f[x][j]\ge f[x][j-1]\),所以 \(f[x+1][j]-f[x][j]=f[x][j-1]+1-f[x][j]\le f[x][j-1]+1-f[x][j-1]=1\)。
若 \(f[x+1][j]=f[x+1][j-1]\),\(f[x][j]\ge f[x][j-1]\),由数学归纳法,\(f[x+1][j-1]-f[x][j-1]\le 1\),所以 \(f[x+1][j]-f[x][j]\le f[x+1][j-1]-f[x][j-1]\le 1\)。
证毕。
有了这个性质又怎么样?得出结论:\(\Delta f\) 是一个 \(01\) 序列,所以可以用一个二进制数 \(S\) 压缩这个差分数组。
因此可以定义出 \(dp[i][S]\):填 \(t\) 的前 \(i\) 位,\(\Delta f[1\sim n][i]\) 为 \(S\) 的方案数。最终 \(i\) 的答案就是 \(\sum dp[m][A]\),其中 \(A\) 是一个包含 \(i\) 个 \(1\) 的二进制数。
例二:BZOJ3591:最长上升子序列
题意:给出 \(1\sim n\) 的一个排列的某一个最长上升子序列(记其长度为 \(m\)),求原排列可能的种类数。\(n\le 15\)。
在这道题目里,内层 DP 就是 "最长上升子序列"。
经过瞪眼法,我们发现 \(f[i]\) 表示前 \(i\) 个数的 LIS 长度没有好的性质。难道要放弃了吗?
转念想到 LIS 的另一种求法:维护 \(f_i\) 表示长度 \(i\) 的 LIS 结尾数最小值。而这个数组就有比较好的性质了:它是单调递增的,而且每新加一个数进来,只会修改一个位置。每个数有三种状态:在 \(f\) 中,曾经在 \(f\) 中,还没考虑。用三进制压缩为 \(S\)。
\(dp[i][S]\) 表示填了前 \(i\) 位,此时 \(f\) 的状态为 \(S\) 的方案数。在转移时强制只能转移到合法的 \(S'\)。具体而言,假设这一步选择填 \(j\),必须满足:① 若 \(j\) 在给定的 LIS 内,要求 LIS 中 \(j\) 之前所有的数都填了;② 要求填了 \(j\) 后前 \(i+1\) 个数的 LIS 长度 \(\le m\)。
标签:le,DP,内层,sim,LIS,dp From: https://www.cnblogs.com/FLY-lai/p/18446710