延迟决策技巧

FLY_lai · 2025-11-05 15:34:11 · 算法·理论

• 给每个对象决策属性，贡献与每个对象的属性相关。

• 如果直接 DP 决策每个对象具体的属性，难以找到一个顺序，使得前面决策的属性不会再影响贡献。

• 有一个单调的简单标准，把所有决策分作两部分：一部分是确定不会再影响贡献的（确定部分）、一部分是有可能会再影响贡献的（待定部分）。已经进入确定部分的决策不会再回到待定部分。

• 确定部分等价。待定部分等价。

• 此时可以考虑记录这个标准，下一个对象的决策分为 "让它的属性作为确定部分" 或 "让它的属性作为待定部分"。同时在标准发生改变的时候再处理那些从待定部分进入确定部分的决策。

一个经典的贡献就是 mex，按什么顺序决策都有可能出现先 1 后 0 导致 mex 直接变到 2。但是 mex 随着出现的数的集合扩大，显然是单调不降的。而且若决策一个数 <\text{mex} 是不会影响 mex 的。

例一：P7213

先考虑按什么顺序。显然要么按值域来看，要么按顺序来看。但是如果按值域来看需要同时处理两个位置，所以我们考虑按顺序。那是从前往后还是从后往前呢？注意前面的数是否会减少，要依赖后面的数，所以我们应该从后往前、这样记录的信息就可以判定当前数要怎么减少。

然后来考察性质。首先如果后面出现了一个数 x，那么前面的数不可能等于 x。进一步观察，我们发现操作其实可以不看作是每一轮都对整体操作，而是转为：从后往前扫，只要当前的数后面出现过就 -1，直到变成 0 或者后面没有。扫完了就得到最终的结果。

所以一个数 x 要变成 0，等价于后面 1\sim x 都出现了。那么我们可以大致得出一个数如果填 x 就有两种可能：

• 若后面 1\sim x 都出现了，变成 0。

• 若后面 1\sim x 里有漏的，变成漏的里最大的。

那么难点就在于我们怎么判断 1\sim x 里有没有漏的。如果具体决策每个数等于几，那就难以避免状态每个数是否出现。但是此时发现有一个单调性：如果已经连续出现了 1\sim x，那么未来连续出现的上限只会比 x 大。所以决策一个数为 \le x 不会改变这个连续高度，而决策 >x 有可能改变。

把当前后缀里的数分为两个部分：1\sim h、\ge h+2 的数。考虑在 DP 过程中记录连续出现的高度，决策下一个数是 \le h 还是 \ge h+2，前者立刻算贡献，后者待定。当 h 发生变化时，决策待定的元素里有哪些要被确定。

设 dp(i,h) 表示 i\sim n 的高度决策好了，最大连续出现高度为 1\sim h 的方案数。

此时我们应该要预见到（或者在下面推的时候碰到）：一种高度只有两个名额，当剩下两个名额或者一个名额，可以做 1 的贡献；如果不剩下名额，就做 0 的贡献。而从两个名额变成一个名额、和从一个名额变成没有名额，这两种变化是本质不同的！所以难道我们要额外记录有多少个高度是两个名额的吗？

这样做复杂度肯定爆炸了。考虑上面遇到的问题，我们可以认为相等的两个数也是有区分的，最终给答案除以 2^n。这样有两个名额的贡献系数就是 2，从而转为有多少个名额可选，贡献系数就是多少。

然后考虑转移到 i-1。设 i\sim n 里有 p_i 个要变成 0，q_i=n-i+1-p_i 个要留下。

• 若 i-1 要变成 0，则 i-1 的高度要 \le h。

  一共有 2h 个名额，但是有 h 个作为 1\sim h 的连续前缀，以及 p_i 个变成 0 的初始高度肯定 \le h，因此被占用了 h+p_i 个名额，剩下 h-p_i 个。

  所以 dp(i,h)\times (h-p_i)\rightarrow dp(i-1,h)。

• 若 i-1 要留下。

  那不会更新 h，先放着在以后考虑。dp(i,h)\rightarrow dp(i-1,h)。

  考虑枚举加入 i-1 后新的连续出现高度 h'。那么要在后面的自由高度里选 h'-(h+1) 个来填补空缺。

  所以后面的数又分成两部分：\le h' 的、>h'+1 的。

  考虑贡献系数。

  1. 先选出哪些位置要来补空缺，方案数 \binom{q_i-h}{h'-(h+1)}。

  2. 然后给 i-1 决策一个初始高度。

     一共 2(h'-h) 个名额，后面要用 h'-(h+1) 个名额，还有 h'-h+1 个名额。

     方案数 h'-h+1。

  3. 最后还要考虑后面的位置怎么选使得能刚好消到 h+2\sim h'。

     显然这个问题等价于 1,1,2,2,\dots,h'-h-1,h'-h-1 里选 h'-h-1 个数出来，操作完了刚好是 1\sim h'-h-1 的排列的方案数。

     但是这个东西不是很好直接求，所以设辅助数组 g_n 表示 "在 1,1,2,2,\dots,n,n 里选 n 个数，操作完了剩下 1\sim n 的排列的方案数"。

     考虑怎么求 g。如何划分状态？

     我们考虑极端值原理，枚举最终 1 号位的高度 x，那么其原本高度在 [x,n] 里有 2(n-x+1) 个名额，而之前用了 n-x 个在 [x+1,n] 里，所以还剩 n-x+2 个名额。 同时我们发现后面最终高度为 1\sim x-1 和 x+1\sim n 的不会相互干扰了（因为没有 x 供给它们跨越中间），所以有转移：

     g_n=\sum_x(n-x+2)\binom{n-1}{x-1}g_{x-1}g_{n-x}

     方案数 g_{h'-h-1}。

  所以 dp(i,h)\times \binom{q_i-h}{h'-(h+1)}(h'-h+1)g_{h'-h-1}\rightarrow dp(i-1,h')。

转移即可，复杂度 O(n^3)。不要忘记最终除以 2^n。

在本题中，单调的标准即 "连续出现高度 h"。如果决策 \le h，不会改变 h；而决策 \ge h+2 可能在后面改变 h，也可能不会影响。于是待定后者的决策即可。

例二：P14364

把计数排列看作天和人的匹配。按值域考虑每个人和哪个匹配。大致为 dp(i,j) 表示 c\le i 的人里有 j 个面试失败的方案数。

然后就发现当决策一个人面试失败的时候并不只涉及 c 比它小的人，因为可以让一个 c 大的人遇到 0，所以还要额外记录后面有多少个人面试失败了。

为了避免记录每个人的状态，我们要考虑这个单调的标准，从而把同属于 "确定" 或 "待定" 的人能同类看待。

把 (i,c_{p_i}) 在坐标系上画成柱状图，画一条左下到右上的折线表示每一天的失败人数变化。这样就容易看出因为折线是单调向上的，所以在某次折线达到 x 的高度后，之后耐心值 \le x 的人都不可能被录取，而 >x 的人只要放在 1 的位置就一定会被录取。这就是单调的标准。

所以考虑把人分作耐心值 \le x,>x 考虑。因为 x 是单调上升的，所以过程中会有一些 >x 的人进入 \le x，但是 \le x 的永远会 \le x。所以 "\le x 的人" 是确定的部分，">x 的人" 是不确定的部分。考虑设 dp(i,j,k) 表示决策前 i 天的安排、有 j 个人失败、有 k 个位置的人耐心值 >j（等待后面决策），在 dp 里只决策前 i 天耐心值 \le j 的方案数。

使用刷表法转移。考虑第 i+1 天的人是要失败还是要通过。记 cnt_i 表示耐心值为 i 的人数，sc 为 cnt 的前缀和。

• 必须失败。分类讨论 $c_{p_{i+1}}$ 与 $j+1$ 的大小关系，并把 $k$ 个人里 $=j+1$ 的纳入考虑。 - $c_{p_{i+1}}>j+1$。 $$ \sum_{w=0}^k\binom{k}{w}\binom{cnt_{j+1}}{w}w!dp(i,j,k)\rightarrow dp(i+1,j+1,k-w+1) $$ - $c_{p_{i+1}}\le j+1$。 $$ \sum_{w=0}^k\binom{k}{w}\binom{cnt_{j+1}}{w}w!(sc_{j+1}-(i-(k-w))dp(i,j,k)\rightarrow dp(i+1,j+1,k-w) $$
• - $c_{p_{i+1}}>j$，此时会录取，$j$ 不变。 $$ dp(i,j,k)\rightarrow dp(i+1,j,k+1) $$ - $c_{p_{i+1}}\le j$，此时会放弃，$j$ 加一。 $$ \sum_{w=0}^k\binom{k}{w}\binom{cnt_{j+1}}{w}w!(sc_{j+1}-(i-k))dp(i,j,k)\rightarrow dp(i+1,j+1,k-w) $$

虽然看起来要枚举 w 是 O(n^4) 的，但因为总人数 O(n)，所以 w 一共只能枚举 n 次。故总复杂度是 O(n^3) 的。

例三：CF1608F

考虑转换计数对象，令 s_i 为 a 的前缀 \text{mex} 数组，对 s 计数再考察一个 s 可以对应多少个 a。

对于 s，显然应该有 s_i\le i 和 s_i\le s_{i+1} 和 s_i\in [b_i-k,b_i+k]。

考虑固定 s 后 a 有多少种选取方案。手玩一下，首先能发现一个简单的性质：s_i\neq s_{i+1} 时，a_{i+1}=s_i。于是这启示我们把 s 分成若干个相等段来考虑。

于是设划分的结果是 [l_1=1,r_1],[l_2=r_1+1,r_2],\dots,[l_k,r_k=n]。每段内的 s 都相等。那么有：

• 对 2\le i\le k 有 a_{l_i}=s_{r_{i-1}}。

• 对 1\le j\le r_i 有 a_j\neq s_{r_i}。

• 为了使 a_{l_i} 一加入，就从 s_{r_{i-1}} 增加到 s_{l_i}，则 a_1\sim a_{r_{i-1}} 必须包含 (s_{r_{i-1}},s_{l_i}) 的所有数。

• 如果 s_1=1 则 a_1=0。

感受一下，以上的条件已经充分了。所以开始 DP：因为有 \text{mex} 运算，所以采用延迟决策、记录待定位置数的方法，f(i,j,k) 表示前 i 个位置，s_i=b_i+j，有 k 个位置上的 a 是没确定的（>s_i 的个数），方案数。

考虑转移。枚举下一位 s_{i+1}=b_{i+1}+p（p\in [-k,k]）：

就算假设那个系数可以 O(1) 求，状态是 O(n^2k) 的，枚举 s_{i+1} 是 O(k) 的，若 s_i<s_{i+1} 还要枚举放多少个下来还是 O(k) 的。复杂度是 O(n^2k^3) 起步，肯定过不了，必须优化。

接下来是一个很有道理但是很巧妙的想法：\text{mex} 只关心每种数是否出现过，那如果我们待定的方式是有 k 种数是 >s_i 的，就非常方便了。所以我们改设 f(i,j,k) 表示前 i 个 s_i=j 有 k 种数待定。

那么 s_i=s_{i+1} 时，a_{i+1} 可以选择新开一种或者选择等于旧的一种。而 s_i<s_{i+1} 时只需要从 k 种里选 s_{i+1}-s_i-1 种就行了！

所以更改了一下定义，轻松就做到了 O(n^2k^2)。但是这个复杂度还是过不了。继续优化。写出转移式子：

现在来优化。前两条不用优化，看看第三条是什么东西，发现枚举 j' 完全不如直接枚举 b_{i+1}+j'-(b_i+j)-1。重写一下就是 f(i,j,k) 会转移到 f(i+1,j+c,k-c) 这条斜线上。用个前缀和优化即可。

upd：有一个聪明的方法可以不用前缀和优化。我们不用 "一次性" 决定好 \text{mex} 要增长到哪里。可以认为 \text{mex} 有两种增长方式：在 a_i 放一个 \text{mex}，或者在目前待定里取一种放 \text{mex}。所以可以写成 f(i,j,k)\leftarrow f(i-1,j-1,k)+f(i,j-1,k+1)\times (k+1)。

例四：图灵杯第七届高级组T1 棋无常树

令 mxb_i 为 i 子树内 b_i 的最大值，则赋值后 i 子树内 0\sim mxb_i-1 都应该出现过。同时 i 子树内 a\neq -1 的数也确定出现过。定义 vis_{i,j}=0/1 表示 i 子树内数 j 是否出现过。

定义 f_{i,j,k=0/1} 表示在 i 子树内填 a，使得 "\neq mxb_i 且不确定是否出现过的数里" 有 j 种不同的数，且 mxb_i 没有出现/出现了 的方案数。所以这个状态实际上把数分成了三类：确定的数、不确定的数、mxb_x，在转移时就要让这三类数指代的对象统一了才能转移。

考虑合并 x 和其子树 i，为了方便起见，不妨 mxb_x\ge mxb_i。记 sz_u 为当前 u 子树内有多少个 a=-1 的，也就是 f 数组的第二维在有意义的前提下最高取到多少。

因为 f 的定义是基于 vis 的，第一个任务是合并 f_x,f_i 的 vis。

当我们发现 vis_{x,p}=1,vis_{i,p}=0 时，我们要把 vis_{i,p} 改成 1，那这会对 f_i 有什么影响？p 本来在 i 的视角下属于 "不确定是否出现过的数"，现在变成确定出现的了。所以：

也就是从 j+1 个不确定的里面选一个 p 出来变成确定的，这样更新一次是 O(sz_i) 的。vis_{x,p}=0,vis_{i,p}=1 的同理对 f_x 更新，一次 O(sz_x)。

这个操作会经常出现，我们称它为 trans。可以发现，当有一个新的确定数出现，为了确保不确定数和确定数之间没有重复，就需要做一次 trans。

然后 vis_x,vis_i 相等了，开始合并 f_x,f_i。为了方便，搞一个 g_{j,0/1} 作为临时数组，f_x*f_i 先放到 g 里面，转移完了再从 g 复制回 f_x。

• 先考虑 mxb_x=mxb_i 的情况。一个 naive 的想法是 f_{x,j,a}\cdot f_{i,k,b}\rightarrow g_{j+k,\max(a,b)}。但这个转移方程是不对的，原因是 x 里的 j 种不同数可能与 i 里的 k 种不同数有重合，导致最终的不同种类数比 j+k 少。

  枚举 j:0\rightarrow sz_x。我们希望 f_{x,j,a}\cdot f_{i,k,b} 可以直接转移，问题在于两棵子树内的不同数会有重合。所以一个想法是随着 j 的变动，始终保持 f_{i,k} 的 k 个不同数里与 f_{x,j} 的 j 个数不重合。

  那么当 j 增大一，我们只需要处理这 k 个不同数里出现了 x 的第 j 种数的情况。怎么处理？这和上面计算 "把 vis_{i,p} 改成 1，那这会对 f_i 有什么影响" 是完全一样的。于是只需要 trans 一遍即可。

• 那么只剩下 mxb_x>mxb_i（开头的时候有不妨 mxb_x\ge mxb_i）。

  容易发现上面 j 增大一就对 f_i 做一次 trans 的想法是可以沿用的。但是现在又增加了一个新的问题：f_{i,k,0/1} 的第三维 0/1 指的是 mxb_i 而非 mxb_x。要想让 f_i 转移到 x 的子树内，又要分类讨论 f_i 里有没有 mxb_x。

  • 如果 vis_{i,mxb_x}=1，那么显然第三维只能取 1。也就是 f_{x,j,a}\cdot f_{i,k,b}\rightarrow g_{j+k,1}。

  • 否则，如果 f_i 里没有 mxb_i：转移方程 f_{x,j,a}\cdot f_{i,k,b}\rightarrow g_{j+k,a}。

  如果 f_i 里有 mxb_i：转移方程 f_{x,j,a}\cdot (k\cdot f_{i,k,b})\rightarrow g_{j+k-1,1}。

我们终于合并了所有子树，太好了！但是现在还需要把 x 的影响加入 f_x 内。这又要根据 a_x,b_x 分类讨论。令 s 表示 x 子树内有多少种确定的数会出现（s=\sum_i vis_{x,i}）。

• 考虑 $a_x$ 赋值成什么： - 赋值成一个新的不确定数。$f_{x,j+1,a}\leftarrow f_{x,j+1,a}+f_{x,j,a}$。 - 赋值成一个确定数或者一个旧的不确定数。$f_{x,j,a}\leftarrow f_{x,j,a}\times (s+j)$。 - 赋值成 $mxb_x$。$f_{x,j,1}\leftarrow f_{x,j,1}+f_{x,j,k}$。 注意让 $sz_x$ 加一。
• 此时无法赋值成不确定数，只能是确定数或者 $mxb_x$。 - $a_x=mxb_x$，那么 $f_{x}$ 的第三维只能是 $1$（必然存在 $mxb_x$）。令 $f_{x,j,1}\leftarrow f_{x,j,1}+f_{x,j,0}$ 然后 $f_{x,j,0}\leftarrow 0$。 - 若在 $x$ 之前已经有 $a_x$ 了，那没有任何影响。 - 否则 $x$ 是一个新出现的确定数，也就是 $vis_{x,a_x}\leftarrow 1$。为了排除 $a_x$ 与不确定数的重复，做一次 trans。
• 若 $mxb_x>b_x$ 或 $a_x=b_x$ 或 $vis_{x,b_x}=1$，那么无解，直接退出。 - $b_x=mxb_x$。 这种情况我们只接受 $f_{x,?,0}$ 的转移。因为如果第三维是 $1$，$x$ 的子树里就出现 $b_x$ 了，无解。所以一开始就让所有 $f_{x,j,1}\leftarrow 0$。 - $a_x=-1$。可以赋值成确定数或旧的不确定数或新的不确定数。如果赋值成新的不确定数，$f_{x,j+1,0}\leftarrow f_{x,j+1,0}+f_{x,j,0}$；如果赋值成旧的不确定数或确定数，$f_{x,j,0}\leftarrow f_{x,j,0}\cdot (s+j)$。 注意 $sz_x$ 加一。 - $a_x\neq -1$。若 $a_x$ 以前出现过，不用管；否则 $vis_{x,a_x}\leftarrow 1$，然后为了排除 $j$ 个不确定数里可能有 $a_x$ 出现，再做一次 trans 即可。 - $b_x>mxb_x$。 这种情况下，最终的 $mxb_x=b_x$，所以最终的 $f_x$ 应该满足所有第三维是 $1$ 的位置都是 $0$。 同时当 $mxb_x\neq -1$，因为 $b_x$ 要满足，$[0,b_x-1]$ 都出现过，所以 $mxb_x$ 也必须出现过。于是只能从原本第三维是 $1$ 的 $f_x$ 转移。 因此要特别注意，现在的 $f$ 第三维指的是 $mxb_x$，需要的 $f$ 第三维指向 $b_x$。 - $mxb_x=-1$。注意这种情况显然应该有 $f_x$ 所有第三维是 $1$ 的位置都是 $0$。 1. $a_x=-1$。可以赋值成新的不确定数或旧的不确定数或确定数。 记得 $sz_x$ 加一。 2. $a_x\neq -1$。若 $a_x$ 之前出现过，不用理；否则 $vis_{x,a_x}\leftarrow 1$ 然后做一次 trans。 - $mxb_x\neq -1$。 1. $a_x=-1$。 如果赋值为一个新的不确定数，就是 $f_{x,j+1,0}\leftarrow f_{x,j+1,0}+f_{x,j,1}$。注意这里只能从 $f_{x,j,1}$ 出发转移。 否则不确定数个数（第二维）不增加，也就是转成旧不确定数或确定数或 $mxb_x$。如果转成旧不确定数，贡献 $j\cdot f_{x,j,1}$；如果转成确定数，贡献 $s\cdot f_{x,j,1}$；如果转成 $mxb_x$，因为 $a_x$ 处有了 $mxb_x$，其他地方就可以使用 $f_{x,j,0}$ 转移了，贡献 $f_{x,j,0}+f_{x,j,1}$。 因此 $f_{x,j,0}\leftarrow f_{x,j,0}+(s+j+1)\cdot f_{x,j,1}$。 然后 $f_{x,j,1}=0$。 记得 $sz[x]$ 加一。 2. $a_x\neq -1$。 这里又要分为 $a_x=mxb_x$ 和 $a_x\neq mxb_x$。 若 $a_x=mxb_x$，那么其他地方有没有 $mxb_x$ 都可以，$f_{x,j,0}\leftarrow f_{x,j,0}+f_{x,j,1}$，然后 $f_{x,j,1}\leftarrow 0$。 若 $a_x\neq mxb_x$，那么其他地方必须有 $mxb_x$，所以 $f_{x,j,0}\leftarrow f_{x,j,1}$，然后 $f_{x,j,1}\leftarrow 0$。同时注意如果 $a_x$ 是新的确定数出现，做一次 trans。 最后，因为 $b_x$ 要满足，还要让一些不确定数变成 $[mxb_x+1,b_x-1]$ 里的数。具体而言就是 $f_{x,i-1,j}\leftarrow f_{x,i,j}\cdot i$，然后让 $sz_x$ 减一。不要忘了让 $mxb_x\leftarrow b_x$。

于是 DP 的部分结束了，怎么计算答案？

令 s=n+1-\sum_i vis_{1,i}-(mxb_1\neq -1)，那么 s 就是不确定数的选择范围。

然后是复杂度分析。

• 合并 vis 数组的复杂度。把 trans 的 O(sz_i) 看作对子树内每个结点增加 1 的势能。对于结点 x 不断向上合并，每增加 1 的势能就表示 vis 出现了一个新的位置变成 1，而一共有 n+1 个位置可以变成 1，所以一个点贡献的总复杂度是 O(n)。于是这一部分总共贡献 O(n^2)。

• 合并 f 数组的复杂度。把 O(sz_x\cdot sz_i) 看作在两棵子树里各选择一个点，在 LCA 处贡献 1 的复杂度。容易分析出 O(n^2)。

• 加入 x 的复杂度。容易做到 O(sz_x) 的复杂度。总共 O(n^2)。

因此总复杂度 O(n^2)。