dp？

点亮花火 · 2026-10-10 15:19:04 · 个人记录

感觉这次是真的可以，写一篇 dp 的东西，但其实还是一个做题记录之类的东西？

贡献延迟计算

在 dp 的过程中你通常会为了避免后效性而在一个位置决策好这个位置的所有贡献、方案，但可能为了避免后效性会使得你的状态数很大，需要记录很多信息。

而我们可以通过延迟计算贡献，即选择时不算贡献，留到后面某个位置计算，或者把贡献拆到后面的位置上。也就是，我们可以延迟确定该位置选择了什么，也可以延迟计算选择的贡献。

AT_arc207_a [ARC207A] Affinity for Artifacts

之前已经写了匹配的做法，考虑一下 dp 延迟钦定怎么做。

我们先假设每次 x \to x-1 都能被完美利用，此时花费是最优的，用 X 减去这个花费得到的就是能够浪费的节约次数，也就是无效操作的次数。

考虑对于一个 i，所有没有在 [1,i] 匹配的 a_p \le i 的物品都会浪费 1，考虑设 f_{i,j,k} 表示考虑前 i 次删除的灯，当前有 j 个 a_p \le i 的未匹配，浪费的次数为 k 的方案数，考虑如何转移。

令 b_i 表示 \sum_p [a_p = i]，s_i = \sum_{j = 0}^i b_j。

分类讨论 i+1 填的是 \le i+1 还是 > i+1，填 > i+1 相当于留出空位，同时枚举 t 表示有多少个 a_p = i+1 的物品放入了前面预留的空格中，这部分方案数为 {b_{i+1} \choose t} {i+1-(s_{i+1} - j) \choose t} t!，注意第二个组合数中是 i 或者 i+1 取决于这一位填的是 \le i+1 还是 > i+1，然后就能转移了。

P14364 [CSP-S 2025] 员工招聘

dp 贡献的延迟决策，可能写的有点绕，但是感觉我可能就是这样理解明白的。

怎么叫延迟决策呢，考虑最终我们要怎么算方案数，对于一个方案假设最终拒绝了 x 个人，则对于 c_i > x 的 cnt 个人是不区分的，这些人可以任意排列，方案数为 cnt!。

其实相当于我们把 c_i \le x 的人全都已经填进了序列，并且计算了方案数，而对于 c_i > x 的人我们为他们在序列中空出了一些位置，把这些人填进每个位置即可，方案数就是排列数。

于是在决策的过程中我们可以时刻把所有人划分为两个集合 S_1,S_2，假设当前已经决策了 j 个人失败，集合 S_1 中的人 p 满足 c_p \le j，集合 S_2 中的人满足 c_p > j，且我们已经对 S_1 集合中的人计算了方案数，而没有对 S_2 中的人计算方案数。

由于前缀中失败的人数是单调不降的，因此人只会从集合 S_2 变为集合 S_1，而不会从 S_1 重新变回 S_2，于是我们可以在一个人从 S_2 变为 S_1 时把它填到前面预留的空位里，计算方案数。

考虑一个从前向后决策的过程需要记录哪些信息，当前失败的人数 j，以及当前预留了 k 个空位给 S_2 集合中的数，于是设 f_{i,j,k} 表示考虑了前 i 天，当前有 j 个人失败了，前 i 天中预留了 k 个空位给当前仍满足 c_p > j 的 p，S_1 集合的方案数。

考虑最终 S_2 集合所有数均满足 c_i > x，于是答案实际上就是 S_1 集合方案数乘上 S_2 集合的排列数，由于我们在一个人从 S_1\to S_2 的时候计算贡献，于是 dp 中最终只计算了 S_1 集合的方案数。

考虑转移，转移时我们需要决策第 i 位要填一个 S_1 中的数还是预留一个空位，同时对于 j 变大时，我们需要把当前 c_p = j 的从 S_2 加入到 S_1 计算方案。考虑其中的一些填入到了前面的空位中，剩下的将会填到后面的格子中。

令 a_i = \sum\limits_j [c_j = i],b_i = \sum\limits_{j \le i} a_j，即 a_i 表示 c_p = i 的 p 的数量，b_i 表示 c_p \le i 的 p 的数量。

若 s_{i+1} = 0，此时该位置无论填什么都必然会增加一个失败的人，于是 j \to j+1。我们先来计算 c_p = j+1 的 p 的贡献，枚举 t 表示有 t 个 c_p = j+1 的 p 放置在了 pos \le i 预留的空位中，剩余的放在后面的格子里。

这部分方案数为 {a_{j+1} \choose t} {k \choose t} t!，即选出 t 个 c_p = j+1 的 p，并从 k 个空位选出 t 个填进去的方案。

若该位置放一个空位，有转移{a_{j+1} \choose t} {k \choose t} t! f_{i,j,k} \to f_{i+1,j+1,k-t+1}
若该位置放一个 c_p \le j+1 的 p，考虑选出这个 p 的方案数为 b_{j+1} - (i - (k-t))，于是有转移{a_{j+1} \choose t} {k \choose t} t! (b_{j+1} - i + k - t)f_{i,j,k} \to f_{i+1,j+1,k - t}

若 s_{i+1} = 1，若填一个 c_p \le j 的数 p，此时同样会使得 j \to j+1，于是选出这个数的方案数为 b_{j} - i + k。同样枚举 t 表示有 t 个 c_p = j+1 的 p 放置在了 pos \le i 预留的空位，有转移

(b_{j} - i + k){a_{j+1} \choose t}{k\choose t} t! f_{i,j,k} \to f_{i+1,j+1,k - t}

否则预留一个空位给 c_p > j 的人，j 不变，k+1，即

f_{i,j,k} \to f_{i+1,j,k+1}

要求通过人数 \ge m，也就是失败人数 \le n - m，枚举失败人数 x，由于是最终状态，我们要求 S_2 中只有 c_p > x 的 p，于是最终答案为 \sum\limits_{j=0}^{n-m} f_{n,j,n - b_j} \times (n-b_j)!。

时间复杂度 O(n^3)。

不知道哪里的题

不是，这个 OJ，这么神秘吗。

根据我们前面总结的东西，可以把所有决策划分为类似两个集合，考虑按照值域扫描，维护 f_{i,j} 表示扫了值域 [1,i]，已经有 j 个数确定了位置的方案数，考虑如何转移。

将 i 匹配给某个 t_i = 1 的 x，记录 a_i 表示 x\le i,t_i = 1 的位置数，b_i 表示 x \le i,t_i = 0 的位置数，我们知道 x \le i,t_i = 0 的匹配的一定是 \le i 的值域，从而可以计算出 x \le i,t_i = 1 匹配了的数量为 j-1 - b_{i-1}，未匹配的数量即为 a_i - (j - 1 - b_{i - 1})，转移 f_{i-1,j-1} \to f_{i,j}。
将 i 匹配给某个 t_i = 0 的 x，此时我们先不计算贡献，而是先给 x 匹配一个黑盒，后面再决策什么东西填进黑盒里，转移有 f_{i-1,j} \to f_{i,j}。
给 x = i,t = 0 的 x 计算贡献，从前面所有未匹配的数中选择一个填进去，系数为 (i - j + 1)，转移 f_{i-1,j - 1} \to f_{i,j}。

真不知道哪里的题

给定 n,m 和长度为 n 的序列 B，对长度为 n 的满足以下条件的序列 A 计数。

对于 1 \le i \le n，满足 \text{mex}(A[1\dots i]) \le mex(B[1\dots i])。

咕咕咕了，真的就是完全没听听懂啊。

AT_utpc2023_p Priority Queue 3

挺不错的延迟决策的题，感觉难的延迟决策其实难点就是你不知道要记多少信息，哎其实 dp 都是吧就是，不知道该设啥。

考虑记录 f_{i,j,k,l=0/1} 表示处理了前 i 次操作，当前最大的未被堆删除的 a 中的数为 a_j，此时堆中有 k 个 a 中的数，a_j 是/否在堆中。

考虑对于 a 序列中的数之间的顺序以及方案，我们留在最大值 j 变化的时候计算贡献，也就是我们把 a 分给了若干个 j 分割成的每一段，在每一段最大值被删除时再计算贡献。

考虑第 i 次操作如何转移，记录 x 为前面执行 + 的次数，y 为前面执行 - 的次数。分 + 和 - 讨论。若该位为 +，考虑加入一个什么样的数：

加入一个不在 a 中的数，此时一共有 n - a_j - (m - j) 个大于 j 的非 a 数，其中堆中有 x - y - k 个，于是系数为 n - a_j - (m - j) - (x - y - k)，有转移 f_{i,j,k,l} \to f_{i+1,j,k,l}。
加入 a_j，此时要求 l 从 0 变为 1，k 变为 k+1。
加入非 a_j 的 a 中的数，我们暂时不决策加入的是什么数，把方案数的贡献延后计算，于是转移 f_{i,j,k,l} \to f_{i+1,j,k+1,l}。

若该位为 - 有：

若 k = 0，显然堆中都没有数，不合法。
若 k > 1，弹出的一定不是最大值，也就是任意一个 a_j，并不关心他们是什么，留到后面计算贡献。
若 k = 1 且 l = 0 则弹出的不是最大值，同样不需要关心弹出的是什么。
否则 k = 1 且 l = 1，此时弹出的时最大值，我们来计算在这段中产生的贡献，设下一个最大值的位置为 p，首先 >p 的 a 中的数一定已经在 j 之前被弹出了，而有 c = b - (m - j) 个在前面弹出了，但还没有决策他们是什么数，我们需要选出 d = j - p - 1 个，作为 a_j \sim a_p 之间的数，于是要乘上一个 A_{c}^d 的系数。

然后我们解决了这个题，看上去复杂度是 O(n^4) 的，但我们只有在 k = 1 的位置会枚举一次 p，也就是对于每对 i,j 只会枚举 O(1) 次 p，因此时间复杂度为 O(n^3)。

很牛的题。哎不是，这题怎么是，小根堆（

贡献拆分

贡献拆分其实和延迟钦定很像，某次决策会产生若干的贡献，而我们把这个贡献拆分给后面被他影响的每个决策上面。比如某次操作贡献为一个增量，我们通过枚举或记录一些东西，从而在这个位置直接算出增量对后面的全部贡献。

线头 dp

线头 dp，其实就是连续段 dp 吧，考虑一些路径问题，比如要求走所有点一次最小化贡献，如果你发现贡献可以独立的拆到每个点上，也就是我们不关心是从哪个点走过来的，就可以记录非常少的信息，而简单维护贡献。

通常贡献是由相邻两项之间产生的，通过 dp 维护已经合法的一些连续段的信息，从而使得新加入一个点时可以合并、延长、新增一个段，状态通常只需要记录段数以及一些边界信息。

感觉说不明白，看个题可能就懂了。

CF704B Ant Man

考虑我们只关心相邻两个点之间产生的距离贡献，这个贡献取决于大小关系，我们从小到大决策每个点放的位置，这样可以确定好大小关心，从而只需要决策这个点在操作序列中位于哪个位置。

我们对操作序列（经过的点的顺序）维护连续段，则 s 位于最左边，e 位于最右边，设 f_{i,j} 表示考虑了编号前 i 的点，当前序列中连续段数量为 j 的最优贡献。

接在右边同理。
合并两个连续段，左右均作为较大的产生贡献。

要注意进行各个操作均会存在一些限制，比如 s,t 若已经合并成了一段就不能加任何点了，以及 s 只能在最左边，t 只能在最右边，实现时注意贡献即可，感觉本质连续段 dp。