插入类 dp 总结

概念

\qquad 什么是插入类 $dp$ 呢？

\qquad 这类题目都有一个特性：1、题目往往会基于一个给定的排列做 $dp$；2、时间复杂度在 $O(n^2)～O(n^3)$ 之间；3、答案和排列中上升、下降的突变位置有较大关系。

\qquad 这类题目的套路也很固定：1、我们考虑将排列中的数按照从小到大的顺序插入其中，并以它为阶段进行状态设计。这样做有一个很好的性质就是前面已经插入的数一定比当前数小，可以不考虑上升下降的限制；2、状态一般设计为：$d{p}_{i,j}$ 表示已经插入了 $1～i$，插入的数字组成了 $j$ 个连续段的方案数。这个连续段要求只要形成就不允许断开，但是段与段之间允许插入新的数字。这样我们可以仅通过合并段、放到段两边、新开一段这三种情况统计出所有的方案数。不过，要注意的是，在这里新开一段与放在段两边属于两种不同的方案，原因就是上面说的段与段之间允许插入新的数字。3、如果题目是最优化问题，涉及到贡献的统计，我们一般采用贡献提前计算的套路。

\qquad 这类题目一般还会限制这个排列的左右端点。在转移时特判左右端点的情况即可。如果没有限制，那我们就要加一维状态表示当前已经确定了几个端点。

例题

Permutation

\qquad 题面

\qquad 很经典的一道题。按照顺序插入的套路当然要使用，不过它的状态不能设计成上文提及的那样。因为这道题中，排列中的数的大小关系已经明确给定而且不规律，我们不能通过记录段数来进行转移。所以我们返璞归真，设 $d{p}_{i,j}$ 表示已经插入了 $i$ 个数，最后一个数在前 $i$ 个数中的相对排名是 $j$ 的方案数。注意是相对排名。为什么这么设计状态就可以呢？因为我们对于第 $i$ 个数可以填什么只跟第 $i?1$ 个数填了什么有关，所以只记录最后一个数的状态足矣。转移分 $>,<$ 两种情况讨论即可，很好转，需要加一个小的前后缀和优化。

\qquad Code

[ABC209F] Deforestation

\qquad 题面

\qquad 我们先考虑如何才能做到代价最小。因为是最优化问题，涉及到了贡献的计算，所以我们考虑贡献提前计算。既然想贡献提前算，考虑三个数之间的贡献是很不好搞的，所以我们考虑 $i$ 与 $i+1$ 之间会产生什么贡献。若先拿走 $i$，产生的贡献是 $a_{i+1}\times 2+a_i$，若先拿走 $i+1$ 产生的贡献是 $a_i\times 2+a_{i+1}$。通过这个不难发现，我们先拿走 $i$ 与 $i+1$ 之间更大的那个显然是更优的。按照这个策略，我们就能轻易的做到代价最小。接下来统计方案该怎么搞呢？

\qquad 因为取数的最优策略已经定了，所以我们从这个策略入手。如果 $a_i>a_{i+1}$，那么我们就会先拿走 $i$，这相当于 $i$ 的相对排名比 $i+1$ 高（假设我们先拿走相对排名高的），$a_{i+1}>a_i$ 同理。如果 $a_i=a_{i+1}$，那么 $i$ 和 $i+1$ 先拿走哪个都无所谓。这样，这道题就转化为了上一题，把上一题的做法套过来即可。

\qquad Code

[CEOI2016] kangaroo

\qquad 题面

\qquad 这道题就可以完美的套用插入类 $dp$ 的所有套路。我们设 $d{p}_{i,j}$ 表示插入了 $1～i$，形成了 $j$ 个连续段的方案数。先不考虑端点，我们插入第 $i$ 个数后有三种情况：1、新开一段。对应了 $d{p}_{i,j}=d{p}_{i?1,j?1}\times j$，因为有 $j$ 个空位可以插入。在前面我们提到，新开一段意味着两边以后可能会插入新的数字，而新的数字一定比 $i$ 大，所以符合题目要求；2、合并两个连续段：$d{p}_{i,j}=d{p}_{i?1,j+1}\times j$。这两个连续段在插入 $i$ 之前就已经存在了，一定比 $i$ 小，符合要求；3、放在一段的边缘。不过，我们想这一情况合法么？放在边缘意味着另一边以后可能会插入更大的数字，这样就不符合题目的要求了。

\qquad 现在，我们考虑有端点的情况。设左右端点分别为 $s,t$。1、新开一段。还是要从 $d{p}_{i?1,j?1}$ 转移而来，不过乘的系数会有所变化。如果有端点已经插入，那么我们就不能在端点外边继续新开一段。所以对应的转移式是：$d{p}_{i,j}=d{p}_{i?1,j?1}\times (j?(i>s)?(i>t))$；2、合并两个连续段。在这里我们要特判端点，因为端点一定不能合并。此时有一个小细节：如果 $i>s\&\&i>t\&\&i<n\&\&j=1$，此时我们是不能转的。因为此时一旦合并，就将 $s$ 和 $t$ 合并为同一段了，不过后面还有数字没插入，一定不合法。剩下的和上边一样。3、放在一段的边缘。有端点之后，不难发现端点可以放在两边两端的边缘。不过 $s$ 只能放在最左边，$t$ 只能放在最右边。这样，这道题就做完了。

\qquad 核心 $Code$：

if(i == s || i == t) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;//可以新开一段放在两边，也可以放在原来最左端、最右端
else {
    if(i > s && i > t && i < n && j == 1) ;
    else dp[i][j] = (dp[i][j] + (1LL * dp[i - 1][j + 1] * j) % mod) % mod;
    dp[i][j] = (dp[i][j] + (1LL * dp[i - 1][j - 1] * (j - (i > s) - (i > t))) % mod) % mod;//可以新开一段，也可以合并两段。 不过新开的时候需要注意不能新开在s,t两边
}

Ant Man

\qquad 题面

\qquad 最优化问题，考虑贡献提前计算。状态设计就是把记方案数改为记最小代价。分的情况与上一题几乎一样，多处理一下放在段两边的情况，贡献简单分讨即可。

\qquad Code

[JOI Open 2016] 摩天大楼

\qquad 题面

\qquad 实在是一道好题。

\qquad 因为本题要求的是 $sum\le L$ 的方案数，所以我们要在状态中加一维 $sum$。又因为本题没有限制端点，所以我们还要再加一维表示确定了几个端点。综上，最终的状态为：$d{p}_{i,j,k,l}$ 表示已经插入了前 $i$ 个数（从小到大排序后），形成了 $j$ 个连续段，这些连续段产生的总代价和为 $sum$，确定了 $l$ 个端点的方案数。由于 $sum$ 这一维的跨度可能会很大，最大范围能到 $nL$，所以如果直接转复杂度为 $O(n^{3}L)$，不可过。我们考虑优化。

\qquad 我们想，如果在相邻两个位置分别填了 $A_1$ 和 $A_2$，那它们产生的代价就是 $A_1?A_2$；如果填了 $A_1$ 和 $A_3$，那代价就是 $A_1?A_3=(A_1?A_2)+(A_2?A_3)$。往后以此类推。发现什么规律了吗？对于当前我们考虑插入的数 $A_i$，我们可以在所有连续段端点处都加上 $A_i?A_{i?1}$，这样并不会影响最终代价的计算，但是它使得 $sum$ 的跨度急剧减小。因为此时 $sum$ 一定是单增的，所以如果此时 $sum>L$ 就不再往下转移即可。时间复杂度降为 $O(n^{2}L)$。

\qquad 核心 $Code$：

int s = (a[i + 1] - a[i]) * (j * 2 - d)/*优化*/ + k, Now = dp[i][j][k][d];
if(s > L || !Now) continue;
dp[i + 1][j + 1][s][d] = (dp[i + 1][j + 1][s][d] + (1LL * Now * (j + 1 - d)) % mod) % mod;//新开一段
if(j >= 2) dp[i + 1][j - 1][s][d] = (dp[i + 1][j - 1][s][d] + (1LL * Now * (j - 1)) % mod) % mod;//合并两段
if(j) dp[i + 1][j][s][d] = (dp[i + 1][j][s][d] + (1LL * Now * (j * 2 - d)) % mod) % mod;//放在段两边
if(d < 2) dp[i + 1][j + 1][s][d + 1] = (dp[i + 1][j + 1][s][d + 1] + (1LL * Now * (2 - d)) % mod) % mod;//增加端点
if(d < 2 && j) dp[i + 1][j][s][d + 1] = (dp[i + 1][j][s][d + 1] + (1LL * Now * (2 - d)) % mod) % mod;

[ZJOI2012] 波浪

\qquad 题面

\qquad 与上一题一模一样，只不过把 $\%mod$ 去掉，最后除一个 $n!$ 即可。

\qquad 这道题最大的坑点在 $K\le 30$，我们需要对“数据范围分治”：对于 $K\le 8$，我们正常用 $double$；对于 $K\le 30$，我们使用 $\_\_float128$ 即可。

\qquad 核心 $Code$（指 $\_\_float128$ 的输出）：

void Print(__float128 ans) {
	int num[maxn];
	num[0] = 0;
	ans = ans * 10;
	for(int i = 1; i < K; i ++) {
		num[i] = (int)ans;
		ans = (ans - num[i]) * 10;
	}
	num[K] = (int)(ans + 0.5);
	for(int i = K; i >= 1; i --) {
		if(num[i] >= 10) num[i] -= 10, num[i - 1] ++;
	}
	printf("%d.", num[0]);
	for(int i = 1; i <= K; i ++) printf("%d", num[i]);
	puts("");
}

Phoenix and Computers

\qquad 题面

\qquad 这道题可以继续沿用上面的套路，但是没必要，因为 $n\le 400$。

\qquad 我们直接大力设状态：$d{p}_{i,j}$ 表示开启了前 $i$ 台电脑，其中有 $j$ 台是手动开的，方案数。在转移前，我们要先预处理一个 $g_i$：完全靠手动开启 $i$ 台电脑的方案数。想求 $g$，我们可以逆向考虑：假设现在有 $i$ 台电脑开着，我们每次只能关最两边的其中一台电脑，求方案数。这个问题很简单：$2^{i?1}$，所以 $g_i=2^{i?1}$。在这之后，我们就可以正常 $dp$ 了：枚举最后一段连续段长度为 $k$，则 $d{p}_{i,j}=d{p}_{i?k?1,j?k}\times g_k\times C_j^k$。

\qquad Code

[COCI2021-2022#2] Magneti

\qquad 题面

\qquad 套路的，我们设计状态：$d{p}_{i,j,k}$ 表示前 $i$ 个磁铁分为 $j$ 组，占用空位数为 $k$ 的方案数。转移正常分类讨论即可。不过，因为我们这里设计的是分了 $j$ 组，而不是有 $j$ 个连续段，所以转移时乘的系数会有所变化。最后统计 $ans$ 时要乘个组合数。这个组合数的含义是将剩下的空位插入到 $n$ 块磁铁之间。根据插板法得到 $ans=\sum d{p}_{n,1,i}\times C_{n+l?i}^n$。

\qquad 核心 $Code$：

dp[0][0][0] = 1;
for(int i = 1; i <= n; i ++) {
	for(int j = 1; j <= i; j ++) {
		for(int k = 1; k <= L; k ++) {
			int &p = dp[i][j][k];
			p = dp[i - 1][j - 1][k - 1];
			if(k > r[i]) p = (p + (2LL * dp[i - 1][j][k - r[i]] * j) % mod) % mod;
			if(k > 2 * r[i] - 1) p = (p + (1LL * (1LL * dp[i - 1][j + 1][k - (2 * r[i] - 1)] * (j + 1)) % mod * j) % mod) % mod;//任取两组合并
		}
	}
}