题单题解 - Der Richter 的动态规划
DerRichter
·
·
算法·理论
Der Richter 的动态规划。
CF2190B2 Sub-RBS (Hard Version)
:::info[题意]{open}
给定 n、仅含 ( 和 ) 的括号串 s,定义一个非空子序列 t 的得分为 t 本身为正则括号序列且存在更优的正则括号子序列时,这些子序列中的最大长度(其中 ( 的字典序小于 ),若为真前缀更短者更劣),否则得分为 0,求所有非空子序列得分之和。
:::
:::success[思路]
首先有两个重要结论:
> **结论 1** $\space$ 一个字符串的得分只有可能为 $0$ 或 $len - 2$,其中 $len$ 为长度。
>
> **结论 2** $\space$ 一个字符串的得分为 $len - 2$,当且仅当这个字符串包含 $)(($ **子序列**。
我们先证结论 1。显然,对于一个合法的括号序列,其合法子序列的长度一定为偶数,所以得分最多为 $len - 2$。
接下来分两种情况。若原串不为合法括号序列,则得分为 $0$。
若原串为合法括号序列,此时可以证明,一定可以构造出长度为 $len - 2$ 的更优子序列。
设原串为 $s$,构造出来的子序列为 $t$,显然 $|s| > |t|$,要使 $t$ 比 $s$ 更优,只能是存在一个 $1 \le i \le |t|$,使得:$s_i = )$ 且 $t_i = ($。
又因为 $t$ 是 $s$ 的子序列,其在选取的时候跳过了 $s$ 的第 $i$ 个字符,即 $)$,那么为了使 $t$ 为合法括号序列,在 $i$ 后面的 $j$,$t$ 一定会又跳过一个 $($,才能使得 $t$ 为合法括号序列。显然,删去一个 $)($ 子序列不会影响合法性,所以 $t$ 一定合法且比 $s$ 更优。
然后来看结论 2。
先证必要性:只有包含 $)(($ 子序列才有可能有得分。
在结论 1 的证明过程中,我们提到,$s$ 至少会包含一个 $)($ 子序列。而删去 $($ 后,在 $i$ 后面至少还要有一个 $($,这样才能够使 $s_i$ 能够取到 $($。所以,$s$ 必定包含 $)(($ 子序列。
再证充分性:包含 $)(($ 的子序列一定都有得分。
在结论 1 的证明过程中也提到,删去一个 $)($ 子序列,并不会影响合法性。这是显然的,请读者自己思考。
我们考虑找到一个 $)($ **子串**,并删去最后一个 $($,显然,这样一定能够构造出一个合法的 $t$。
证明就到这里。所以这个问题被转化为;统计所有是合法括号序列且包含 $)(($ 子序列的子序列,并求它们的 $len - 2$ 之和。
考虑动态规划。定义状态 $dp_{i, pre, k = 0/1/2/3}$ 表示,当前考虑前 $i$ 个位置,在当前选择的子序列中,将 $($ 看作 $1$,$)$ 看作 $-1$,累加和为 $pre$,子序列 $)(($ 匹配到第 $k = 0/1/2/3$ 位时的**方案数**,另外再记录一个 $sum_{i, pre, 0/1/2/3}$,表示同样状态下的**长度和**。
考虑转移。首先显然这一位可以不选:
$$
dp_{i, pre, k} \leftarrow dp_{i - 1, pre, k}
$$
$$
sum_{i, pre, k} \leftarrow sum_{i - 1, pre, k}
$$
考虑当前为 $)$ 的情况。显然可以使 $k$ 从 $0$ 变为 $1$:
$$
dp_{i, pre, 1} \leftarrow dp_{i - 1, pre + 1, 0}
$$
$$
sum_{i, pre, 1} \leftarrow sum_{i - 1, pre + 1, 0} + dp_{i - 1, pre + 1, 0}
$$
考虑当前为 $($ 的情况。显然可以使 $k$ 从 $1$ 变为 $2$ 或从 $2$ 变为 $3
dp_{i, pre, 2} \leftarrow dp_{i - 1, pre - 1, 1}
sum_{i, pre, 2} \leftarrow sum_{i - 1, pre - 1, 1} + dp_{i - 1, pre - 1, 1}
dp_{i, pre, 3} \leftarrow dp_{i - 1, pre - 1, 2}
sum_{i, pre, 3} \leftarrow sum_{i - 1, pre - 1, 2} + dp_{i - 1, pre - 1, 2}
注意,如果 pre 满足对应要求(> 0 或 < n),则只能够进行 k 变化的转移,不能进行不选择的转移,否则会重复计数。最后答案即为 sum_{n, 0, 3} - 2 \times dp_{n, 0, 3}。这里可以滚动数组优化。
:::
CF2194F1 Again Trees... (Easy Version)
:::info[题意]{open}
给定一棵树,每个结点有一个权值 a_i,再给定一个不可重集合 b,其大小为 k,用一个序列 \{ b_k \} 表示。求原图中满足以下条件的边集数量:
- 在原图中,对于删去这个边集中的所有边后所形成的每个连通块,都满足:连通块内所有结点的权值异或和均属于集合 b。
:::
:::success[思路]
Easy version 的入手点在于,$k$ 的范围极小,这点在上面的题意中也有所凸显。
首先容易想到一个暴力树形 DP。状态:$dp_{u, x}$ 表示,考虑 $u$ 的子树中,包含 $u$ 的连通块异或和为 $x$ 的方案数。转移根据删/不删 $(u, v)$ 边分类讨论即可得出。
但是这样,状态空间是会爆炸的。原因很显然,$x$ 并不一定 $\in b$。因为 $u$ 可能并不是包含 $u$ 的那个连通块中深度最浅的点。
但是话又说回来了,我们发现,$u$ 的子树中,除了包含 $u$ 的这个连通块可能并不完全属于 $u$ 的子树,其他的连通块都包含于 $u$ 的子树。也即我们设:
$$
S = \left\{ \bigoplus \limits _ {i \in T} b_i \mid T \subseteq \{ 1, 2, \dots, k\} \right\}
$$
定义状态:$dp_{u, s}$ 表示,考虑 $u$ 的子树,除了包含 $s$ 的那个连通块,其他的连通块的异或和为 $s$ 的方案数。容易发现,$s \in S$ 是一定成立的。此时状态空间 $O(16n)$,不会爆炸。
对于 $u$ 的一个儿子 $v$,我们按边 $(u, v)$ 是否删去的两种情况来作讨论。下面,我们记
$$
sum_u = \bigoplus _ {v \text { in subtree of } u} a_v
$$
即,$sum_u$ 表示 $u$ 子树的异或和。
1. 不删去边 $(u, v)$。此时 $u$ 和 $v$ 同属一个连通块,设 $v$ 子树中包含 $v$ 的连通块大小为 $sum_v \oplus t$,显然 $t \in S$,那么转移如下:
$$
dp'_s \leftarrow \sum \limits _ {\substack{v \text { is son of } u \\ t \in S}} dp_{u, s \oplus t} \times dp_{v, t}
$$
其中 $dp'$ 为处理完儿子 $v$ 后 $dp_u$ 的真实值。
2. 删去边 $(u, v)$.此时 $u$ 和 $v$ 分属两个连通块,设 $v$ 子树中包含 $v$ 的连通块大小为 $sum_v \oplus t$,要求 $sum_v \oplus t \in b$。此时 $t$ 子树内所有的连通块对于 $u$ 来说,全都变为了不包含 $u$ 的其他连通块,即应当全部计入新的状态。根据上面的要求,$sum_v \oplus s \in S$ 一定成立。
所以转移如下:
$$
dp'_{s} \leftarrow \sum \limits _ {\substack{v \text { is son of } u \\ t \in S \\ sum_v \oplus t \in b \\ sum_v \oplus s \in S}} dp_{u, s \oplus sum_v} \times dp_{v, t}
$$
按照上述方法转移即可。注意,这里 $s$ 一维需要离散化,且需要对于每个 $S_i \oplus S_j$ 预处理出其排名,以便直接处理转移。
:::
## [P15804 [GESP202603 八级] 消息查找](https://www.luogu.com.cn/problem/P15804)
:::info[题意]{open}
有 $n$ 条消息,每一条消息可以引用前面的消息,也可以不引用。对于消息 $i$ ($1 \le i \le n$),以 $r_i$ 标记消息 $i$ 是否有引用,以及所引用的消息编号。若 $r_i > 0$,则消息 $i$ 为引用了消息 $r_i$;若 $r_i = 0$,则消息 $i$ 没有引用消息。
要求实现一个消息定位工具。如果当前位于消息 $i$ ($1 < i \le n$),那么接下来可以选择以下两种操作之一:
- 定位到消息 $i - 1$;
- 如果消息 $i$ 引用了消息 $r_i$,定位到消息 $r_i$。
以上操作可以执行任意次(包括零次)。给出 $q$ 次查询,每次查询两个正整数 $x_i > y_i$,表示询问从 $x_i$ 定位到 $y_i$ 最少需要多少次操作。
:::
:::success[思路]
下文中 $m$ 表示有引用的消息总数。
显然,每个查询的答案,就相当于选择若干不相交的区间 $(r_j, j]$ 使得其长度之和最大。我们设其为 $val_i$,则答案为:
$$
ans_i = x_i - y_i - val_i
$$
然后这个看起来就像一个 DP 不是么。我们考虑使用一次引用 $j$。那么,$r_j$ 之前的情况就是一个子问题,所以可以考虑 DP。
我们设计状态:$dp_k$ 表示,考虑前 $k$ 条引用消息时的 $\max val$。然后考虑转移:
1. 不使用引用。则显然有
$$
dp_k \leftarrow dp_{k - 1}
$$
2. 使用引用。考虑第 $k$ 条引用消息,其能够使用的最大前提是 $r_k \ge y$,于是我们设 $pre_k$ 表示右端点 $\le r_k$ 的引用消息数量,然后
$$
dp_k \leftarrow dp_{pre_k} + (k - r_k + 1)
$$
显然 $pre_k$ 可以在 $O(m \log m)$ 的时间复杂度内预处理。
因为每次的 $y$ 不一样,所以我们每次都需要重新 DP,但由于 $m \le 10 ^ 3$,所以总时间复杂度:
$$
O(m \log m + qm)
$$
勉强通过。
:::
## [P15862 [LBA-OI R3 B] 回去!](https://www.luogu.com.cn/problem/P15862)
:::info[题意]{open}
给定一张图,每个点的出度均为 $1$,每个点有一个字符。现在要在图上游走。首先,在图上等概率均匀随机地选择一个起点,然后用一个栈记录起点到当前点上路径的点,初始栈为空。每一步都有两种选择:
- 前进:沿着当前点的唯一出边行走,并将到达的点加入栈,概率为 $p$;
- 后退:弹出栈顶,回到之后的栈顶,若此时栈为空则回到起点,概率为 $1 - p$。
每走完一步,当前点的字符会被加入一个字符串中。现在要走 $2k$ 步,求结果字符串前 $k$ 位与后 $k$ 位相等的概率
:::
:::success[思路]
首先,我们可以把游走过程分为两段:第 $1$ 步到第 $k$ 步,以及第 $k + 1$ 步到第 $2k$ 步。
我们枚举起点,然后立即就可以得出沿着出边一直走的长度为 $2k + 1$ 的路径。我们从这 $2k$ 个点中,选取一个点,作为第二段的起点,显然起点的出点和该起点的出点的字符应当相等。
两端起点都确定后,我们考虑动态规划。设状态 $dp_{i, x, y}$ 表示,当前两段各走了 $i$ 步,第一段走到 $x$ 处,第二段走到 $y$ 处的概率,其中 $1 \le x, y \le 2k + 1$。
接下来考虑转移。
我尝试过把所有情况都在这里列出来,但是失败了。因为实在是太多了。
我们分为 $4$ 个方向处理。如果遇到 $x$ 或 $y$ 等于 $1$ 的情况且需要前进的时候,把对应概率改为 $1$ 即可。因为在起点只能向右移动。
我们设两段字符串的起点为 $2$ 和 $v$,则初始状态是 $dp_{1, 2, v}$,因为此时已经匹配了一个。
在 DP 时,我们先不处理第 $k$ 步,即两端交接的那一步。这个情况需要单独处理。我们枚举第二段终点,显然第一段终点和第二段起点一定要相邻,且两段各走了 $k$ 步。这样最终状态就确定了。
注意最后输出的是 $nP$,直接对每个起点的概率求和输出即可。
:::
## [AT_dp_w Intervals](https://www.luogu.com.cn/problem/AT_dp_w)
:::info[题意]{open}
考虑一个长度为 $N$、仅由 `0` 和 `1` 组成的字符串。该字符串的分数按照如下方式计算:
- 对于每个 $i$($1 \leq i \leq M$),如果从第 $l_i$ 个字符到第 $r_i$ 个字符之间至少包含一个 `1`,则将 $a_i$ 加到分数上。
请你求出字符串分数的最大值。
$1 \le N \le 2 \times 10 ^ 5, |a_i| \le 10 ^ 9$。
:::
:::success[思路]
我们先来考虑如何设计状态。我们从左往右构造字符串,考虑一个题目给定区间 $[l, i]$:
- 若字符串第 $i$ 位为 $1$,显然该区间一定得分;
- 若字符串第 $i$ 位为 $0$,那么字符串 $[l, i)$ 区间内至少出现一个 $1$ 才能得分。
所以,一个区间 $[l, i]$ 是否得分,取决于:
1. 第 $i$ 位是否为 $1$;
2. 若第 $i$ 位为 $0$,之前的 $1$ 的分布方式。
但是显然我们无法随时记录前面 $1$ 的分布情况。注意到,我们设定当前位为 $0$,那么 $[l, i]$:
- 当最后一个 $1$ 的位置 $\ge l$ 时,得分;
- 当最后一个 $1$ 的位置 $\lt l$ 时,不得分。
所以,一个状态中只需要记录**最后的 $1$ 的位置**即可。
于是我们定义状态:$dp_i$ 表示,当前最后一个 $1$ 的位置是 $i$ 时的最大价值。并记 $dp_0 = 0$,表示没有 $1$ 时没有价值。
考虑转移。我们考虑区间 $[l, i]$,分情况讨论:
1. 若第 $i$ 位为 $1$:此时 $[l, i]$ 一定有价值,可以从前面的任意状态转移而来:
$$
dp_i \leftarrow \max \limits _ {0 \le j \lt i} dp_j + \sum \limits _ {r_k = i} a_k
$$
2. 若第 $i$ 位为 $0$:此时 $[l, i]$ 有价值当且仅当 $[l, i)$ 内存在至少一个 $1$,不能更新 $dp_i$,而是应当以当前区间的价值更新前面的状态:
$$
dp_j \leftarrow dp_j + a \space (\forall j \in [l, i))
$$
其中 $a$ 为区间 $[l, i]$ 的价值。
显然这个 DP 过程可以使用线段树维护。
:::
## [P11233 [CSP-S 2024] 染色](https://www.luogu.com.cn/problem/P11233)
:::info[题意]{open}
给定一个长度为 $n$ 的正整数数组 $A$,其中所有数从左至右排成一排。
你需要将 $A$ 中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分:
设 $C$ 为长度为 $n$ 的整数数组,对于 $A$ 中的每个数 $A_i$($1 \leq i \leq n$):
- 如果 $A_i$ 左侧没有与其同色的数,则令 $C_i = 0$。
- 否则,记其左侧**与其最靠近的同色数**为 $A_j$,若 $A_i = A_j$,则令 $C_i = A_i$,否则令 $C_i = 0$。
你的最终得分为 $C$ 中所有整数的和,即 $\sum \limits_{i=1}^n C_i$。你需要最大化最终得分,请求出最终得分的最大值。
:::
:::success[思路]
若某个位置 $i$ 要产生贡献,那么必然存在一个位置 $j < i$,满足:
- $a_j = a_i$;
- $i, j$ 染成相同颜色;
- 区间 $(j, i)$ 中的所有位置都染成另一种颜色。
最后一点尤为重要:由于只有红、蓝两种颜色,若 $i$ 与 $j$ 同色,且 $j$ 是 $i$ 左侧最近的同色位置,那么 $j + 1, \dots, i - 1$ 必须全部与它们异色。
首先很容易想到一个暴力 DP:设 $dp_i$ 表示前 $i$ 个数的最大得分。但转移时,很难判断第 $i$ 个位置能否产生贡献,因为我们并不能从前面的状态 $dp_j$ 中获取能够影响 $a_i$ 贡献的决定性因素,换言之没有记录最后一个与 $a_i$ 同色的位置。
因此,我们需要在 DP 状态中增加一个条件,让中间区间的颜色能够确定。设 $dp_j$ 表示考虑前 $j + 1$ 个数,且要求第 $j$ 个位置与第 $j + 1$ 个位置颜色不同的情况下的最大得分。
为了方便转移,额外设一个虚拟位置 $a_0 = 0$,并令 $dp_0 = 0$。因为题目保证所有 $a_i \ge 1$,所以该虚拟位置不会产生贡献。
考虑转移。设当前计算 $dp_{i - 1}$,注意不是 $dp_{i}$。这个状态就限定了 $i$ 和 $i - 1$ 的颜色不同。设 $j$ 是位置 $i$ 左侧最近的、与位置 $i$ 颜色相同的位置。那么:
- 必有 $j \le i - 2$,因为前面已经限定位置 $i - 1$ 与 $i$ 异色;
- 区间 $[j+1,i-1]$ 全部与位置 $i$ 异色,因此这一整段颜色相同;
- 位置 $j$ 与 $j + 1$ 异色,恰好符合状态 $dp_j$ 的限定条件。
于是,$dp_{i - 1}$ 可以从 $dp_j$ 转移而来。你可能会问:这个状态是如何想到的呢?其实,就是把**最近同色位置**转化成一个可以枚举的边界。
我们先考虑朴素转移。即枚举合法 $j$ 然后转移。我们考虑一段前缀中,如果全部染成同色,能够产生的贡献 $S_r$。则
$$
S_r = \sum \limits _ {i = 2} ^ r [a_i = a_{i - 1}] a_i
$$
前面已经提到,从 $dp_j$ 转移到 $dp_{i - 1}$(其中 $0 \le j \le i - 2$),那么位置 $j + 1$ 到 $i - 1$ 都被染成了同一种颜色。容易发现,其中相邻且数值相同的位置产生的贡献为
$$
S_{i - 1} - S_{j + 1}
$$
至于位置 $i$,如果 $a_j = a_i$,它就可以与位置 $j$ 同色并获得 $a_i$ 的贡献;否则没有额外贡献。
因此
$$
dp_{i - 1}= \max _ {0 \le j \le i - 2} \left( dp_j + S_{i - 1} - S_{j + 1} +[a_j = a_i] a_i \right)
$$
接下来考虑优化。我们发现,朴素转移方法中,最耗时的是枚举所有 $j$。我们首先把当前的区间贡献提前维护起来。
我们使用一个线性表 $v$。在处理位置 $i$ 之前,定义
$$
v_j = dp_j + \sum_{k = j + 2} ^ {i - 1} [a_k = a_{k - 1}] a_k
$$
也就是说,$v_j$ 表示状态 $dp_j$ 加上从它出发、把后续位置染成同色时,已经能够获得的相邻相等贡献。
于是转移简化成
$$
dp_{i - 1} \leftarrow \max_{0 \le j \le i - 2} \left(v_j + [a_j = a_i] a_i\right).
$$
现在只剩下一个问题:怎样快速求这个最大值?我们记 $p = pos_{a_i}$,其中 $p$ 是 $a_i$ 在 $[1, i - 2]$ 中最后一次出现的位置;若没有出现,则令 $p = -1$。
分类讨论。
当 $j > p$ 时,因为 $p$ 是最近一次出现 $a_i$ 的位置,所以 $a_j \ne a_i$,这些状态转移到当前位置时都没有额外贡献,因此只需要查询
$$
\max_{p + 1 \le j \le i - 2} v_j
$$
即可。
当 $j \le p$ 时,状态 $p$ 的候选值为 $v_p + a_i$。所以整个转移变成
$$
dp_{i - 1} \leftarrow \max \left( \max_{p + 1 \le j \le i - 2} v_j, v_p + a_i \right)
$$
特别地,当 $p = -1$ 时,第二项不存在,只需查询区间 $[0, i - 2]$ 的 $v$ 值即可。
前面解释了如何转移。但是还需要维护贡献:当 $a_i = a_{i - 1}$ 时,相邻的两个数如果染成相同颜色,就可以获得 $a_i$ 的贡献。对于所有之前已经存在的候选状态 $v_j$,只要 $j \le i - 2$,它们都可以让位置 $i - 1$ 和 $i$ 染成同色,从而多获得 $a_i$。
因此,当 $a_i = a_{i - 1}$ 时,需要执行
$$
v_j \leftarrow v_j + a_i \space (0 \le j \le i - 2)
$$
所以,我们可以使用线段树来维护线性表 $v$。注意区间右端点是 $i - 2$,**不包含**刚刚建立的新状态 $dp_{i-1}$。因为这个新状态要求位置 $i - 1$ 与 $i$ 异色,两者不能因为数值相同而直接取得相邻贡献。
注意,应当在计算完 $dp_i$ 后更新 $pos_{a_{i - 1}}$,也是因为上面的原因。
:::
## [P9100 [PA 2020] Miny](https://www.luogu.com.cn/problem/P9100)
:::info[题意]{open}
给定 $n$ 个地雷,编号为 $1, 2, \dots, n$。每个地雷 $i$ 具有一个位置坐标 $a_i$ 和一个爆炸半径 $r_i$。且满足 $a_1 < a_2 < \dots < a_n$。若第 $i$ 个地雷被引爆,那么所有满足 $|a_j - a_i| \le r$ 的地雷 $j$ 均会被引爆。初始时可以选择一个地雷集合 $S$,引爆这个集合内所有的地雷。求最后结果的总数,模 $10 ^ 9 + 7$。
:::
:::success[思路]
我们先考虑暴搜的状态来推导 dp 状态。然后就会发现,暴搜的状态只能够暴力记录集合 $S$,这样的时间复杂度显然是错的。
所以我们定义状态:$dp_i$ 表示仅考虑前 $i$ 个地雷的引爆情况,且钦定第 $i$ 个地雷不被引爆的方案数。这样就满足了动态规划的无后效性原则。
考虑转移。如果从 $j$ 转移到 $i$,那么需要满足 $j$ 到 $i$ 之间(开区间)的所有地雷不能引爆 $j$ 或 $i$。我们定义 $pre_i$ 和 $nxt_i$ 分别表示第 $i$ 个地雷左边/右边第一个能够引爆 $i$ 的地雷下标。那么 $j$ 和 $i$ 应当满足:$pre_i \le j$ 且 $nxt_j \ge i$。转移就是这样:
$$
dp_i \leftarrow \sum \limits _ {j = pre_i} ^ {i - 1} dp_j [nxt_j \ge i]
$$
显然这样是 $O(n ^ 2)$ 的,需要考虑优化。我们可以把上式拆成前缀和相减的形式:
$$
\sum \limits _ {j = 0} ^ {i - 1} - \sum \limits _ {j = 0} ^ {pre_i - 1}
$$
这样就可以树状数组“离线”处理了。时间复杂度 $O(n \log_2 n)
| 至于 pre 和 nxt 数组,单调栈正反两遍 O(n) 即可求出。 |
P10138 [USACO24JAN] Cowmpetency G
:::info[题意]{open}
给定整数 N, Q, C,求满足条件的整数序列 c_1, c_2, \dots,c_N 的数量,答案对 10 ^ 9 + 7 取模。
要求:
- 对所有 i,有 1\le c_i\le C。
- 给定 Q 对数 (a_i,h_i),其中 1 \le a_i < h_i \le N。
- 对每一对 (a_i,h_i),位置 h_i 是第一个满足
c_{h_i} > \max _ {1 \le j \le a_i} c_j
的位置,即
c_k \le \max _ {1 \le j \le a_i} c_j \quad (a_i < k < h_i)
保证所有 a_i 互不相同,且至少存在一个合法序列。
:::
:::success[思路]
定义:
$$
M_i = \max _ {1 \le j \le i} c_i
$$
即前缀最大值。我们称位置 $i$ 为**记录位置**,当且仅当:
$$
c_i > M_{i - 1}
$$
且钦定 $1$ 为记录位置。考虑一条约束 $(a, h)$,条件等价于:
$$
c_h > M_a \qquad c_{k} \le M_a \qquad (a < k < h)
$$
所以,按照记录位置的定义:
- 位置 $h$ 必定为记录位置;
- $(a, h)$ 间的所有位置都不能为记录位置。
容易证明,这两条和所给约束是充要的。
据此,我们可以把所有位置分为三类:
1. 必为记录位置;
2. 不能为记录位置;
3. 自由位置,即随意选择。
显然对于约束 $(a, h)$,只需把区间 $(a, h)$ 定为禁止,$h$ 定为必须即可。
由于 $N$ 较大,我们考虑从 $C$ 入手。定义状态 $dp_i$ 表示,已经处理的前缀的最大值恰好为 $i$ 时的方案数。显然 $i \in [1, C]$。
考虑初始状态。显然 $c_1$ 可以为任何值。当 $c_1 = i$ 时,显然前缀最大值只可能为 $i$。所以,初始时
$$
dp_i = 1 \qquad (1 \le i \le C)
$$
为了方便表示下文的转移,先定义前缀和:
$$
pre_i = \sum \limits _ {j = 1} ^ i dp_i
$$
考虑转移。因为 $N$ 过大,但是这个状态仍然需要枚举下标,又发现类别相等的位置会形成一段区间,所以我们可以把上面的分段点整理出来,去重后再枚举。设我们当前需要考虑长度为 $L$ 的一段连续区间
1. 当前区间内所有的点都**必须成为记录位置**。我们在处理约束的时候,每次都会把一个单点定为必须,所以这种情况一定是一个个单点。设此前最大值为 $p < i$,显然有
$$
ndp_i \leftarrow \sum \limits _ {p = 1} ^ {i - 1} dp_p
$$
即
$$
ndp_i \leftarrow pre_{i - 1}
$$
2. 当前区间内所有的点都**不能成为记录位置**。这个区间内所有的元素都要且只要满足 $1 \le c_j \le i$。所以每一个元素都有 $i$ 中方案。所以
$$
ndp_i \leftarrow i ^ L dp_i
$$
3. 当前区间内所有的点都可以随意选择类别。分两种情况讨论:
- 第一种情况:原来的最大值已经是 $i$。要使处理之后,最大值依然是 $i$,则选择方案数的上一个情况一样,即
$$
i ^ L dp_i
$$
- 第二种情况:原来的最大值为 $p < i$。要使处理之后,最大值达到 $i$,则该区间内至少存在一个 $i$。考虑容斥计算方案数。首先所有元素都在 $[1, i]$ 内随意选择的方案数为
$$
i ^ L
$$
然后,不存在 $i$ 的方案数,即只在 $[1, i)$ 内选择的方案数为:
$$
(i - 1) ^ L
$$
所以,两式相减
$$
i ^ L - (i - 1) ^ L
$$
而最大值 $< i$ 的方案数一共有
$$
\sum \limits _ {p = 1} ^ {i - 1} dp_p = pre_{i - 1}
$$
种。所以这种情况的贡献为
$$
[i ^ L - (i - 1) ^ L] pre_{i - 1}
$$
所以,总体转移为
$$
ndp_i \leftarrow i ^ L dp_i + [i ^ L - (i - 1) ^ L] pre_{i - 1}
$$
如何判断一个分段点对应的是哪种类别?对于点 $i$:
1. 若存在一个 $h_j = i$,那么其为记录位置;
2. 若存在一个 $(a_j, h_j)$ 满足 $a_j < i < h_j$,那么其必须不为记录位置;
3. 若没有找到,显然它是自由的。
:::
## [P9871 [NOIP2023] 天天爱打卡](https://www.luogu.com.cn/problem/P9871)
:::info[题意]{open}
有 $n$ 天,每天可以选择**打卡**或**不打卡**。
- 每打卡一天,能量值减少 $d$。
- 不能连续打卡超过 $k$ 天,即不能出现连续 $k+1$ 天全部打卡的情况。
- 有 $m$ 个挑战,第 $i$ 个挑战要求区间 $[l_i,r_i]$ 内的所有天都打卡,满足后获得 $v_i$ 的能量,其中 $l_i=x_i-y_i+1$,$r_i=x_i$。
- 每个挑战只要满足条件就能获得奖励,多个挑战可以同时完成。
求一种打卡方案,使得 $n$ 天结束后的能量值最大。
等价于:选择若干天打卡,在不存在长度为 $k+1$ 的连续打卡区间的前提下,最大化
$$
\sum _ {\text {已完成的挑战 } i} v_i - d \times \text {打卡天数}
$$
注意:能量值允许为负数。
$\color {red} 1 \le n \le 10 ^ 9$。
:::
:::success[思路]
设当前选择打卡区间为 $[L, R]$,那么若某一个挑战 $[l_i, r_i]$ 包含于 $[L, R]$,即
$$
L \le l_i \le r_i \le R
$$
那么可以获得该挑战的能量收益 $v_i$。又因为我们选择的若干打卡区间之间至少有一天不打卡,即
$$
R_{i - 1} + 2 \le L_i, \qquad i > 1
$$
所以问题转化为:
- 求若干不相交且长度 $\le k$ 的区间,使得打卡收益减去打卡花费最大。
先不管 $N = 10 ^ 9$ 的逆天数据范围,我们依然定义状态:
- $dp_i$ 表示前 $i$ 天的最大能量。
考虑转移。设最后一次打卡区间为 $[L, R]$,则依照上述要求,有转移:
$$
dp_R \leftarrow \max \Big \{ dp_{R - 1}, \max _ L \Big (dp_{L - 2} - (R - L + 1)d + \sum _ {L \le l_i \le r_i \le R} v_i \Big ) \Big \}, \qquad \max \{ 1, R - k + 1 \} \le L \le R
$$
观察到,如果一个打卡区间没有获得挑战奖励,那么直接删去这个区间,一定不会使答案更劣。所以,我们可以令 $R$ 为某个 $r_i$。也即我们只需要在 $r_i$ 处转移。
接下来考虑优化转移。在转移式中把与 $L$ 无关的项移到外面:
$$
dp_R \leftarrow \max \Big \{ dp_{R - 1}, -dR + \max _ L \Big (dp_{L - 2} + (L - 1)d + \sum _ {L \le l_i \le r_i \le R} v_i \Big ) \Big \}
$$
不妨设
$$
f(L) = dp_{L - 2} + (L - 1)d + \sum _ {L \le l_i \le r_i \le R} v_i
$$
上式变为:
$$
dp_R \leftarrow \max _ {\max \{ 1, R - k + 1 \} \le L \le R} \Big \{ dp_{R - 1}, -dR + \max _ L f(L) \Big \}
$$
接下来只需考虑如何递推地维护 $f(L)$ 即可。容易发现,对 $f(L)$ 产生贡献的,无不可分为以下两种:
1. 挑战奖励。我们当前处理到 $R = r_i$,那么对于所有 $L \le l_i$,都要使
$$
f(L) \leftarrow f(L) + v_i
$$
这是一个区间修改。
2. DP 值产生的贡献。计算出 $dp_R$ 后,因为要递推地维护 $f(L)$,对于所有
$$
L - 2 \ge R
$$
的 $L$,都应该使
$$
f(L) \leftarrow f(L) + dp_R - dp_{R - 1}
$$
这也是一个区间修改。
求 $dp_R$ 时,只需区间查询
$$
[\max \{ 1, R - k + 1 \}, R]
$$
即可。这可以使用线段树维护。
还没完呢。前面忽略了 $N = 10 ^ 9$ 的范围而使用了状态空间为 $O(n)$ 的 DP,要缩减状态空间。考虑
$$
f(L) = dp_{L - 2} + (L - 1)d + \sum _ {L \le l_i \le r_i \le R} v_i
$$
随着 $L$ 的增大:
1. $dp_{L - 2}$ 只可能在 $L = r_i + 2$ 时发生变化;
2. 奖励和只可能在 $L = l_i + 1$ 时发生变化;
3. 而 $(L - 1)d$ 是一个线性增加的项。
又因为 $d > 0$,所以在一段没有变化的区间内,$f(L)$ 一定是单调递增的,只需取最右端的值。所以,只需要维护以下位置:
$$
\{ 1 \} \cup \{ l_i \} \cup \{ r_i \} \cup \{ r_i + 1 \}
$$
这些位置都是 $f(L)$ 除 $(L - 1)d$ 这一项外变化的位置的前一位,也即没有变化的区间右端点。
:::
## [P7519 [省选联考 2021 A/B 卷] 滚榜](https://www.luogu.com.cn/problem/P7519)
:::info[题意]{open}
在某地进行了一场 ICPC 竞赛,我们只关心其滚榜环节。共有 $n$ 支队伍参赛,$i$ 号队伍在封榜前通过的题数为 $a_i$。按照过题数从大到小进行排名,若两支队伍过题数相同,则编号小的队伍排名靠前。
滚榜时主办方以 $b_i$ 不降的顺序依次公布了每支队伍在封榜后的过题数 $b_i$(最终该队伍总过题数为 $a_i + b_i$),并且每公布一支队伍的结果,排行榜上就会实时更新排名。现在不知道队伍被公布的顺序,也不知道最终排行榜上的排名情况,只知道每次公布后,本次被公布结果的队伍都成为了新排行榜上的第一名,以及所有队伍在封榜后一共通过了 $m$ 道题(即 $\sum_{i = 1}^{n} b_i = m$)。求最终排行榜上队伍的排名情况可能有多少种。
$\color {red} 1 \le n \le 13, 1 \le m \le 500$。
:::
:::success[思路]
首先,$n$ 极小,可以考虑状压 DP。首先,第一个被公示的队伍过题数应当超过所有队伍。设第 $i$ 个队伍作为第一个被公示的队伍时,需要增加的最少题数为 $st_i$。则
$$
st_i = (\max a) - a_i + [i > p]
$$
其中,$p$ 为满足 $a_p = \max a$ 的最小 $p$。这是因为,第 $i$ 支队伍首先要和当前最大的队伍齐平,如果 $i$ 比当前最大的队伍编号大,那么还需多过一题才能成为榜一。
然后,我们设 $d_{i, j}$ 表示,如果第 $j$ 支队伍紧接着第 $i$ 支队伍被宣布,那么第 $j$ 支队伍**在封榜后**至少需要比第 $i$ 支队伍在封榜后多过的题数。则
$$
d_{i, j} = \max (0, a_i - a_j + [j > i])
$$
因为 $b_i$ 不降,所以 $d_{i, j} \ge 0$。于是,我们设最终公示顺序为排列 $p$,则
$$
b_i \ge st_{p_1} + \sum \limits_{k = 2}^i d_{p_{k - 1}, p_k}
$$
将 $\sum b$ 展开,可得:
$$
m = \sum b \ge n \times st_{p_1} + \sum \limits_{k = 2}^n (n - k + 1) \times d_{p_{k - 1}, p_k}
$$
于是,我们设状态 $dp_{S, i, c}$ 表示,当前选择的集合为 $S$,最后被公示的队伍是 $i$,当前代价为 $c$ 时的方案数。则
$$
dp_{S \cup \{ j \}, j, c + (n - k) \times d_{i, j}} \leftarrow dp_{S, i, c}
$$
其中 $k = |S|$,初始状态为 $dp_{\{ i \}, i, n \times st_i} = 1$。因为实际上 $c \le m$ 的状态都可以被算作答案,所以最终结果为:
$$
\sum \limits_{i = 1}^n \sum \limits_{c = 0}^m dp_{\{ 1, 2, \dots, n \}, i, c}
$$
:::
## [CF2159D1 Inverse Minimum Partition (Easy Version)](https://www.luogu.com.cn/problem/CF2159D1)
:::info[题意]{open}
给定一个长度为 $n$ 序列 $a$。定义一个序列的价值为,其最后一个元素与序列最小值的比值向上取等后的结果。现在要求对原序列进行划分,使得每一段的代价之和最小。
$1 \le n \le 4 \times 10 ^ 5, 1 \le a_i \le 10 ^ {18}$。
:::
:::success[思路]
我们先说结论。
> **结论 1** $\space$ 我们只需保留原序列中的**严格后缀最小值**(即满足 $a_i < \min \limits_{j = i + 1}^n a_j$ 的 $a_i$),对这个序列求出来的答案与原序列相同。
>
> **结论 2** $\space$ 对于最优划分后的序列,每个子段的代价只可能为 $1, 2, 3$。
先看结论 1。我们考虑一个非严格后缀最小值 $a_i$,当其作为划分的右端点时,我们只需把这个端点移至 $i$ 后面的第一个后缀最小值 $j$,答案不会更劣。因为即使右端点后移使得最小值变化,也只会变为该后缀最小值,使得代价变为 $1$。
再看结论 2。我们考虑最优划分(假设)中一个代价 $> 3$ 的子段。设该子段值为 $b_1, b_2, \dots, b_k$,其代价为 $x = \big \lceil \frac {b_k} {b_1} \big \rceil > 3$。显然其长度 $k \ge x$,否则全部划分为单点答案一定更优。子段的最小值为 $b_1$,我们找到一个 $p$,使得 $p$ 为最大的满足 $b_p \le 2b_1$ 的下标。我们将这个子段划为 $[1, p]$ 和 $[p + 1, k]$ 两部分。
- 对于第一部分,显然其代价 $\le 2$;
- 对于第二部分,最小值由 $b_1$ 变为了一个 $> 2b_1$ 的值,其代价必然 $\le \big \lfloor \frac x 2 \big \rfloor$。
综上,最后的代价 $\le 2 + \big \lfloor \frac x 2 \big \rfloor \le x$,这个式子在 $x > 3$ 时成立。所以这样改变一定不会更劣。可以证明,优化到最后,整个序列的代价只会由 $\{ 1, 2, 3 \}$ 组成。
读者可以思考,为什么 $x = 3$ 的情况没法被优化掉?尝试自行构造反例。
所以定义状态:$dp_i$ 表示以 $i$ 为右端点的划分方案的最小代价。下面我们设序列 $c$ 为只保留严格后缀最小值的序列 $a$。
考虑转移。首先 $c_i$ 单独成段:
$$
dp_i \leftarrow dp_{i - 1} + 1
$$
然后,考虑最后一段的代价为 $2$ 或 $3$ 的情况。
我们设:
- $L_2$:满足 $2c_{L_2} \ge c_i$ 的最小下标;
- $L_3$:满足 $3c_{L_3} \ge c_i$ 的最小下标。
最后一段代价为 $2$:
$$
dp_i \leftarrow \min \limits_{j = L_2}^{i - 1} (dp_{j - 1} + 2)
$$
代价为 $3$:
$$
dp_i \leftarrow \min \limits_{j = L_3}^{i - 1} (dp_{j - 1} + 3)
$$
我们发现,$dp_i$ 是**单调不减**的。我们考虑 $c_i$ 的所属:
1. 若 $c_i$ 单成一段,那么去掉后答案减少 $1$;
2. 若 $c_i$ 作为前面的子段的结尾,那么去掉后答案一定不会变大,因为 $c_i$ 严格递增。
去掉最后一个元素的答案即为 $dp_{i - 1}$。所以 $dp_{i - 1} \le dp_i$ 是成立的。
所以,看似需要数据结构优化转移,其实直接取 $L_2 - 1$ 和 $L_3 - 1$ 即可。
:::
## [P9352 [JOI 2023 Final] 训猫 / Cat Exercise](https://www.luogu.com.cn/problem/P9352)
:::info[题意]{open}
给定一棵 $N$ 个点的树,每个点有一个高度 $a_i$,且高度互不相等。有一只可爱小猫,初始时在最高的点上。每次可以选择一个点放置障碍,然后可爱小猫会按照如下方式移动:
- 若可爱小猫当前所在的位置没有障碍,则无事发生;
- 若可爱小猫当前所在的位置,以及其所有相邻位置上都有障碍,可爱小猫就会似在你面前;
- 否则,可爱小猫会选择当前可达点(即到达路径上没有障碍的点)中,高度最高的点,按照最短路径移动。
在可爱小猫似掉之前,请你求出她最大可以移动多少距离,这是可爱小猫的临终遗愿,你一定要满足她呢。
:::
:::success[思路]
我们按高度从高到低来 DP。定义状态 $dp_u$,表示从 $u$ 开始最多可以走多少步。这里的状态隐含了这样的条件:比当前猫塔高度更高、无法再参与后续移动的部分已经被排除,后续目标位于更低高度的连通块中。
对于猫塔 $u$,如果它能够转移到某个低高度连通块的代表 $v$,那么这一段会产生 $\text {dis} (u, v)$ 次移动,之后还能获得 $dp_v$ 次移动。因此:
$$ dp[u] = \max_v \left \{dp_v + \text {dis} (u, v) \right\} $$
其中,$v$ 是与 $u$ 相邻的低高度连通块中高度最高的点。若不存在这样的连通块,则 $dp_u = 0$。
为什么只需考虑高度最高的点?先说结论:
> **结论** $\space$ 对于小猫下一步即将前往的连通块 $C$,设 $v$ 为其中高度最高的点,对于 $C$ 中任意一个点 $w$,都有:
>
> $$
> dp_v \ge dp_w + \text {dis} (v, w)
> $$
>
> 这个式子的意义是,从 $dp_v$ 转移,答案不会比从其他点转移更劣。
接下来给出证明。
显然 $w = v$ 时不等式成立。否则,我们设在 $v$ 放置障碍后,$w$ 所在的连通块为 $D$。我们可以通过封死通往其他不包含 $w$ 的连通块的路径来强制让小猫走向 $D$。设 $D$ 中最高点为 $v'$。则由转移式:
$$
dp_v \ge dp_{v'} + \text {dis} (v, v')
$$
而显然
$$
dp_{v'} \ge dp_w + \text {dis} (v', w)
$$
我们运用树上距离三角不等式:
$$
\text {dis} (v, w) \le \text {dis} (v, v') + \text {dis} (v', w)
$$
得到
$$
dp_v \ge dp_w + \text {dis} (v, v') + \text {dis} (v', w) \ge \text dp_w + {dis} (v, w)
$$
故命题得证。
具体地,如何转移?我们从高度低的塔开始,从下往上转移。我们可以用并查集来维护一个连通块内最高的点,具体的,我们从低到高枚举高度 $h$,然后可以得到高度为 $h$ 的点 $u$。我们从 $u$ 的邻居中,寻找高度 $< h$ 的点 $v$,我们可以从这个连通块内转移。然后并查集的作用就体现出来了,我们使用并查集获取 $v$ 连通块内最高的点 $v'$,按照上述方式转移后,把 $v'$ 的父亲(并查集中)设为 $u$,表示 $v'$ 连通块内最高的点为 $u$。至于计算树上距离,方法多种多样,这里不赘述。
猫一开始位于高度为 $N$ 的猫塔上,因此答案是 $ dp_{p_N} $,其中 $p_i$ 表示满足 $a_j = i$ 的 $j$。
:::
## [[ABC424G] Set list](https://www.luogu.com.cn/problem/AT_abc424_g)
:::info[题意]{open}
有 $N$ 个 idol,另有 $M$ 首歌。每首歌需要 $B_i$ 个 idol 跳舞,而每个 idol 最多可以跳 $A_i$ 场舞。现在要开一张演唱会,需要选出若干首歌,使得每首歌都有足够的 idol 跳舞,且每个 idol 跳舞的场数不能超过各自的限制。每首歌另有一个价值 $C_i$,求选出的所有歌的 $C_i$ 总和最大值。
$\color {red} 1 \le n, m \le 100$。
:::
:::success[思路]
这看着就很像背包啊。很像,很像啊。
首先有一个显然的错误解法。我们求出 $\sum a_i$,然后直接 01 背包:
$$
dp_i \leftarrow dp_{i - B_i} + C_i
$$
其中 $1 \le i \le S$。
那么这个错在哪里呢?~~首先如果这是对的那么这题就不可能放在 G~~,其次,在这个做法中,同一个 idol 对于同一首歌的贡献**可能被重复计算**。比如 $N = M = 2, A = [100, 0], B = [2, 2]$,此时 $S = 100 \ge B_1 + B_2$ 显然成立,但是显然这个 idol 不能分裂成两个跳舞,至少题目不允许。
接下来讲正解。我们考虑一个歌曲子集 $T$,其大小 $|T| = t$。这些歌总共需要
$$
\sum \limits _ {j \in T} B_j
$$
次舞蹈。我们考虑第 $i$ 个 idol,在所有歌曲中,她最多能够贡献多少次舞蹈呢?显然为
$$
\min \{ A_i, t\}
$$
次。所以,$T$ 子集合法,当且仅当
$$
\sum \limits _ {j \in T} B_j \le \sum \limits _ {i = 1} ^ N \min \{ A_i, t \}
$$
我们考虑背包 DP。定义状态:$dp_{i, j, s}$ 表示,考虑前 $i$ 首歌,选取 $j$ 首,$\sum B = s$ 时的最大 $\sum C$。
如何转移?我们将 $B$ 从大到小排序,此时每次转移时添加的歌曲一定是最小的。每次添加后,我们都判断一遍 $s \le \sum \min \{ A_i, j \}$ 是否满足即可,此时判断的是最终选取的歌曲子集中**最大的 $j$ 个**的合法性。
为什么只需要判断最大的 $j$ 个?因为不等式右边只与 $t$ 有关,要使整个集合都满足要求,那么前 $k$ 大一定要满足。即,前 $k$ 大满足,是整个集合满足的**充要条件**,这里 $1 \le k \le t$,$t$ 为最终选取歌曲数。
所以,最终转移为:
$$
dp_{i, j, s} \leftarrow dp_{i - 1, j - 1, s - B_i} + C_i
$$
其中
$$
B_i \le s \le \sum \limits _ {k = 1} ^ N \min \{ A_k, i \}
$$
:::
## [P13785 [eJOI 2022] Longest Unfriendly Subsequence](https://www.luogu.com.cn/problem/P13785)
:::info[题意]{open}
给定一个长度为 $n$ 的序列 $a$。定义一个序列 $b$ 为不友好的,当且仅当:
- 不存在下标对 $(i, j)$ 使得 $|i - j| \le 2$ 且 $b_i = b_j$。
求 $a$ 中最长不友好子序列长度。
:::
:::success[思路]
如果依然沿用常规子序列 DP 的状态:$dp_i$ 表示最后一个选取 $i$ 的最优方案,你会发现这个很没前途啊,因为转移过于复杂,不便优化,这里也不写了,毕竟是错误做法。
我们先不考虑在 $N$ 为十万级别能够通过的做法,先来想暴力状态设计。我们发现,如果记录选出子序列的后两个元素,就可以简化转移。于是尝试定义状态:
- $dp_{i, j}$ 表示选取的子序列最后两个元素依次为 $a_j, a_i$($a_j$ 先于 $a_i$)时的最优方案。
显然 $j < i$ 且 $a_i \neq a_j$ 时这个状态才能合法。于是转移:
$$
dp_{i, j} \leftarrow \max \Big \{ 2, 1 + \max _ {\substack{k < j \\ a_k \neq a_j, a_k \neq a_i}} dp_{j, k} \Big \}
$$
这显然是 $O(n ^ 3)$ 的,无法通过此题。这个应该可以优化到 $O(n ^ 2 \log n)$ 级别,但因为状态空间有 $O(n ^ 2)$,所以还是去不掉这个平方。
于是考虑优化状态。我们发现,$j$ 只需取值于 $[1, i)$ 区间内离 $i$ 最近的 **5 个不同数的最后出现位置**,令其为 $pre_i$。证明如下:
1. 首先,我们可以钦定所有 $j$ 都是 $a_j$ 在 $[1, i)$ 中的最后出现位置。因为子序列的合法性与其中数值在原序列中的下标无关,只与数值有关,且取最后一个一定不会比取前面的更劣;
2. 我们考虑把某个位置 $p$ 插入当前子序列:
$$
\dots, h, j, \color {red} p \color {black}, i, s, \dots
$$
依照要求,有:
$$
a_p \notin \{ a_h, a_j, a_i, a_s \}
$$
由鸽巢原理,一定存在至少一个 $p \in pre_i$,使得其满足上述要求。因为 $a_h, a_j, a_i, a_s$ 至多有 $4$ 种取值,如果候选集合大小至少为 $5$,那么一定可以找到符合要求的转移。
证毕。于是我们可以把状态定义改为:
- $dp_{i, j}$ 表示选取的子序列最后两个元素依次为 $a_{\color {red} pre_{i, j}}, a_i$ 时的最优方案。
转移变为:
$$
dp_{i, j} \leftarrow \max \Big \{ 2, 1 + \max _ {\substack{k < j \\ a_k \neq a_{\color {red} pre_{i, j}}, a_k \neq a_i}} dp_{\color {red} pre_{i, j} \color {black}, k} \Big \}
$$
这样时间复杂度就由 $O(n ^ 3)$ 变为了 $O(25n) = O(n)$,状态空间也大幅缩减。
:::
## [AT_npcapc_2024_o New School Term](https://www.luogu.com.cn/problem/AT_npcapc_2024_o)
:::info[题意]{open}
给定 $2N$ 个点,要求将其划分为两个大小相同的组。给定 $M$ 个要求,每个要求用 $(u_i, v_i)$ 表示,其含义为 $(u_i, v_i)$ 不能在同一个组内,否则就要承受 $2 ^ i$ 的代价。求代价最小的情况下,每个点属于哪个组。
:::
:::success[思路]
这是一道值得反复品鉴的好题。我尽量把所有细节都讲清楚。
下面设 $V = 2N$。
首先,若干个不互相矛盾的不同组的要求,可以构成一个二分图。而维护二分图的一个经典技巧就是扩展并查集,又称拆点。具体地,在本题中,可以把点 $i$ 拆成两个 $i, i + 2N$,分别表示 $i$ 在两个点集中的点。举一例:若 $u, v$ 在并查集内联通($u + V, v + V$ 同样联通,这点在维护的时候会保证),那么 $u, v$ 同色,否则 $u, v$ 异色,且此时有 $u, v + V$ 联通和 $u + V, v$ 联通。还需要对于每个连通块根节点都维护其所统辖的连通块内的黑/白色点数量,这个在合并两连通块时可以维护。
因为以任意 $> 1$ 的数为底数的幂函数都是递增的,这个自己对 $f(x) = 2 ^ x$ 求导就可以得到;所以显然是先满足靠后的要求。所以,我们可以贪心地从后往前加边,每个要求就是一条跨越两集合之间的边。
显然二分图中会存在多个连通块。因为当前可能存在若干点没有要求限制,而这些点间显然不需要连边。设第 $i$ 个连通块的黑/白色节点个数分别为 $a_i, b_i$,而题目要求两组大小相等,则应当确定是否存在一个长度为连通块个数的序列 $t$,使得
$$
\sum t_i = N, \qquad t_i \in \{ a_i, b_i \}
$$
这里又有一个技巧。我们可以把 $sum = \sum \min (a_i, b_i)$ 作为基础,然后把每个连通块看作一个重量 $w = |a_i - b_i|$ 的物品。是否存在合法的方案,就等价于是否可以选取若干个物品,使得重量和恰好为 $N - sum$。
然后,我们考虑第 $i$ 个要求 $(u_i, v_i)$。
若此时 $u, v$ 两点的关系已经确定,即 $u, v$ 联通或 $u, v + V$ 联通,那么此时这个要求的代价已经确定,可以直接跳过。
若此时 $u, v$ 两点的关系尚未确定,我们需要考虑这个要求是否需要被满足。下面来说明一下两个连通块合并后黑/白色点的个数变化。设此前两连通块黑/白色点的个数分别为 $(c_{u, 0}, c_{u, 1})$ 和 $(c_{v, 0}, c_{v, 1})$,合并后黑/白色点的个数分别为 $(c_0, c_1)$。
若 $u, v$ 异色,则
$$
c_0 = c_{u, 0} + c_{v, 1}, \qquad c_1 = c_{u, 1} + c_{v, 0}
$$
若 $u, v$ 同色,则
$$
c_0 = c_{u, 0} + c_{v, 0}, \qquad c_1 = c_{u, 1} + c_{v, 1}
$$
如果使用普通背包 DP,那么每次都要重新跑一遍,时间复杂度高达 $O(N ^ 3)$,会起飞。
但是有一种东西叫作可撤销背包 DP。我们考虑将上面的可行性背包 DP,改为方案数 DP。这样一来,就可以支持撤销了,具体地,只需要减去方案数即可。判断是否可行,也只需判断对应的 $dp$ 值是否非零即可。但是方案数太大了,容易起飞,于是我们将其对一个大质数取模。至于为什么是个大质数,因为要减小方案数能够被其整除的概率。具体地,增加一个物品:
```cpp
if (!w) return;
for (int i = w; i <= n; i++) {
dp[i] = (dp[i] - dp[i - w] + MOD) % MOD;
}
```
删去一个物品:
```cpp
if (!w) return;
for (int i = n; i >= w; i--) {
dp[i] = (dp[i] + dp[i - w]) % MOD;
}
```
注意一定要判断 $w = 0$ 的情况。这样单次更新就是 $O(N)$ 的了。
关于如何维护 $sum$,如下:若 $u, v$ 异色,那么
$$
sum \leftarrow sum - (\min (c_{u, 0}, c_{u, 1}) + \min (c_{v, 0}, c_{v, 1})) + \min (c_{u, 0} + c_{v, 1}, c_{u, 1} + c_{v, 0})
$$
此时需要在 DP 中删去 $(c_{u, 0}, c_{u, 1})$ 和 $(c_{v, 0}, c_{v, 1})$,加入 $(c_{u, 0} + c_{v, 1}, c_{u, 1} + c_{v, 0})$。
判断完异色之后,如果非法(即 $dp_{N - sum} = 0$),那么需要继续令 $u, v$ 同色,此时
$$
sum \leftarrow sum - \min (c_{u, 0} + c_{v, 1}, c_{u, 1} + c_{v, 0}) + \min (c_{u, 0} + c_{u, 1}, c_{v, 1} + c_{v, 0})
$$
删去 $(c_{u, 0} + c_{v, 1}, c_{u, 1} + c_{v, 0})$,加入 $(c_{u, 0} + c_{u, 1}, c_{v, 1} + c_{v, 0})$ 即可。
最终还要构造答案。我们可以按照上面的技巧重新做一遍可行性 01 背包 DP,然后记录每个连通块是否被选中。按照是否被选中来划分集合即可。这里放一份片段,细节有点多:
```cpp
pair<bool, int> ndp[2N];
bool inst0[4N];
...
int target = n - sum;
ndp[0] = {1, 0};
for (int i = 1; i <= (V << 1); i++) {
if (find(i) != i) continue;
int j = find(i <= V ? i + V : i - V);
if (i > j) continue;
int root = cnt[i].first <= cnt[i].second ? i : j;
int w = abs(cnt[root].first - cnt[root].second);
inst0[root] = 1;
if (!w) continue;
for (int k = target; k >= w; k--) {
if (!ndp[k].first && ndp[k - w].first) {
ndp[k] = {1, root}, pre[k] = k - w;
}
}
}
for (int k = target; k; k = pre[k]) {
int r = ndp[k].second;
inst0[r] = 0;
int s = find(r <= V ? r + V : r - V);
inst0[s] = 1;
}
```
建议自己磕出做法,不要看我写的,实在调不出再来看。这样对你的实力提升较大。
:::
## [P17833 [CSP-S 2026] 迁徙 / migrate](https://www.luogu.com.cn/problem/P17833)
:::info[题意]{open}
给定 $N$ 个坐标严格递增的岛屿,坐标为 $a_1, a_2, \ldots, a_N$,以及一个距离限制 $d$。
从岛屿 $i$ 可以直接飞到岛屿 $j$,当且仅当:
$$
|a_i - a_j| \le d
$$
统计有多少对起点、终点,使得从起点到终点恰好存在两条不同的最短路线。
$1 \le n \le 2 \times 10 ^ 6$。
:::
::::success[思路]
给一个不要 dp of dp 的正经 DP 做法。感谢 @yuhong056 dsa 给我的做法,不然我都不会想做这个题,快去 % 他。
这种 -S 正赛题最精了,他可以出得没有任何过难的算法,但你还是做不出。而且平方级暴力 DP 简直没有一点可优化的空间,直接 ban 掉数据结构,最克我这种人了。
回到正题。首先,容易知道,两点间的最短路数量,等于最短路上经过的每一段间的最短路径数乘积。这个是一个再简单不过的乘法原理。
而题目要求有 $2$ 条最短路径的点对个数,也就意味着,每一段的最短路径数只能长这样:
$$
1 \times \dots \times 1 \times \color {red} 2 \color {black} \times 1 \times \dots \times 1
$$
设某一满足要求(最短路径数为 $2$)的点对间,有 $(x, y)$ 两点间的最短路径有两种选择,对应上面的 $2$,且 $(x, y)$ 是**最近的**满足上述要求的点对。有如下结论:
> **结论 1** $\space$ $(x, y)$ 间的最短路长度一定为 $2$。
>:::info[证明]
>显然不可能为 $1$。当长度 $\ge 3$ 时,总可以从两边去掉一些点,使得最短路长度变短,与最近这一前提条件相悖。
>:::
> **结论 2** $\space$ $(x, y)$ 间如果有 $x \rightarrow a \rightarrow y$ 与 $x \rightarrow b \rightarrow y$($a < b$)两种走法,则一定不存在 $x \rightarrow c \rightarrow y$,使得 $a < b < c$。这个显然。因为只有两种走法。但是你会得到一个奇妙的结论:$b = a + 1$。
> **结论 3** $\space$ 设 $L_u, R_u$ 分别为点 $u$ 往左/右走最远能够到达的点编号,则 $a = R_x, b = L_y$。
> :::info[证明]
> 因为 $(x, y)$ 间最短路长度为 $2$,所以 $x, y$ 一定可以直接到达 $a, b$,也就等价于
> $$
> a \le R_x, \qquad b \ge L_y
> $$
> 故 $a, b$ 的合法取值区间为
> $$
> [R_x, L_y]
> $$
> 容易知道,这个区间内的所有点都可以被取为 $a, b$。而由上一个结论:$b = a + 1$,代表该区间长度为 $2$,故
> $$
> a = R_x, \qquad b = L_y
> $$
> :::
于是问题被转化为:有多少 $(p, q)$ 分别能够衔接至 $x, y$ 且 $p \rightarrow x$ 和 $q \rightarrow y$ 分别只有一条路径。
设状态 $dp_i$ 表示,有多少个 $j < i$ 满足:
- $j$ 无法跨越 $i$ 且 $j \rightarrow i$ 只有一条路径。
考虑第 $j$ 个点对 $dp_i$ 的贡献:
1. $i = j$,即最短路长度为 $0$。此时贡献为 $1$。
2. $j \rightarrow i$ 的最短路长度为 $1$。此时需要满足:
$$
R_j = i, \qquad L_i \le j
$$
但是这样直接求有点麻烦。考虑将 $R_j = i$ 稍作变换:
$$
R_j = i \iff X_i \le X_j + d < X_{i + 1} \iff X_i - d \le X_j < X_{i + 1} - d \iff \boxed {L_i \le j < L_{i + 1}}
$$
于是这部分 $j$ 的贡献为 $\min (i, L_{i + 1}) - L_i$。
3. $j \rightarrow i$ 的最短路长度 $> 1$。我们选取 $j \rightarrow i$ 路径上的倒数第二个点 $k$,即 $j \rightarrow \dots \rightarrow k \rightarrow i$。此时需要满足:
$$
R_k = i, \qquad L_i = k
$$
容易发现,这里 $k$ 所满足的条件比第二条的更为严苛。因为要保证 $k$ 为最小的可取值,否则会算重。这个条件等价于
$$
R_{L_i} = i
$$
若 $i$ 满足上述条件,则可以从 $dp_{L_i}$ 转移而来。而 $k = L_i$ 的贡献在第二条中已计算过,所以要 $-1$。
总之,这部分的转移为:
$$
dp_i \leftarrow 1 + \min (i, L_{i + 1}) - L_i + [R_{L_i} = i] (dp_{L_i} - 1)
$$
右边的同理。读者可以自行推导。
求出左右两边的 $dpl_i, dpr_i$ 后,考虑枚举 $x, y$,计算如何求出满足条件的 $p, q = p + 1$ 个数。应当满足:
$$
L_x = p, \qquad R_y = q
$$
依照上面的变换方法,得
$$
L_{p + 1} \le x < L_{p + 2}, \qquad R_{p - 1} < y \le R_p
$$
还要考虑 $x < p, y > q$。我们知道,这些区间里的 $x, y$,对于答案分别都有一些基础贡献:
$$
C_x = \min (p, L_{p + 2}) - L_{p + 1}, \qquad C_y = R_p - \max (p + 1, R_{p - 1})
$$
还要加上左右两侧只有一种情况的贡献。左边,只有 $dpl_{L_{p + 1}}$ 对于 $C_x$ 有贡献。
:::info[证明]
反证法。设我们当前固定一组满足条件的 $x, y$:
$$
R_x = p + 1, \qquad L_y = p
$$
假设 $x > L_{p + 1}$。
因为 $x > L_{p + 1}$,所以必然存在边 $x \rightarrow p$ 和 $x \rightarrow p + 1$。又 $L_y = p$,所以 $p \rightarrow y$ 和 $p + 1 \rightarrow y$ 必然存在。
故从 $x$ 到 $y$ 至少有两条路径:$x \rightarrow p \rightarrow y$ 和 $x \rightarrow p + 1 \rightarrow y$。
设 $j \le L_{p + 1}$。我们要证明,任意一个满足 $j \rightarrow x$ 最短路唯一 $j$,都不可能给答案带来贡献。设 $\operatorname {dis} (j, x) = h, z = L_{p + 1}$,则
- $z \rightarrow p + 1$ 存在;
- $L_p \le z$;
- 对于任意 $z \le t < p$,$t \rightarrow p$ 存在。
我们取 $j \rightarrow x$ 最短路上最后一个中转点 $t$。显然 $j \le t < x < p$。分两种情况讨论:
1. $t \ge z$。因为 $t \ge z = L_{p + 1} \ge L_p$,故 $t \rightarrow p$ 存在。于是可以直接走:
$$
j \rightarrow \dots \rightarrow t \rightarrow p \rightarrow y
$$
这条最短路的长度为 $h + 1$。而经过 $x$ 的两条最短路:
$$
j \rightarrow \dots \rightarrow t \rightarrow x \rightarrow p \rightarrow y
$$
$$
j \rightarrow \dots \rightarrow t \rightarrow x \rightarrow p + 1 \rightarrow y
$$
长度均为 $h + 2$。所以,原来的最短路结构被破坏。
2. $t < z$。因为 $t \rightarrow x$ 存在,且 $t < z < x$,故 $X_x - X_z < X_x - X_t \le d$,所以 $t \rightarrow z$ 也存在。此时可以构造出三条路径:
$$
j \rightarrow \dots \rightarrow t \rightarrow x \rightarrow p \rightarrow y
$$
$$
j \rightarrow \dots \rightarrow t \rightarrow x \rightarrow p + 1 \rightarrow y
$$
$$
j \rightarrow \dots \rightarrow t \rightarrow z \rightarrow p + 1 \rightarrow y
$$
这些最短路的长度均为 $h + 2$。与前文所述有两种方案相悖。
故结论成立。
:::
右边是同理的。而且取左边、右边的 $dp$ 值,分别有前提条件:
$$
L_{R_{p + 1}} = p, \qquad R_{L_{p}} = p + 1
$$
这个读者可自己思考。记得算贡献的时候要 $-1$,因为已经计算过基础贡献了。
::::