[CF2159D2] Inverse Minimum Partition (Hard Version) 题解

· · 题解

上大分场，Div. 2 Rank 8，紫名祭。

不妨设值域为 V。首先你需要发现一堆有关 a 与 f(a) 的性质。

:::info[性质一]{open}

下文中，「a_i 是后缀最小值」当且仅当 a_i \lt \min_{j = i + 1}^n a_j。

我们发现，对于 a_i，如果存在 j 满足 j \gt i, \forall k \in [i, j), a_k \ge a_j，那么让 a_i 作为子段的结尾一定不优。即，当且仅当 a_i 是后缀最小值时，位置 i 才可能作为子段的结尾。同理，当且仅当 a_i 是后缀最小值时，位置 i + 1 才可能作为子段的开头，否则一定不优。

于是，我们只需要关注原序列中是后缀最小值的元素。

:::

:::info[性质二]{open}

考虑对于一个非空数组，什么时候最优的划分方案是一定其本身（即不进行划分）。

设 c 是一个非空数组，我们将其分为两个非空子段 a, b。根据性质一，我们可以认为 a, b, c 均单调递增。容易发现，\mathrm{cost}(a) \cdot \mathrm{cost}(b) \lt \mathrm{cost}(c)。要使 c 的最优的划分方案一定是其本身，那么一定有 \mathrm{cost}(c) \lt \min\{\mathrm{cost}(a) + \mathrm{cost}(b)\}。解一下这两个方程，就可以得到 \mathrm{cost}(c) \le 3。

即，在最优划分中，每个子段的代价一定是 1, 2, 3 中的一个。

:::

:::success[D1 做法]{open}

我们只用关注是后缀最小值的元素。

设 dp_i 表示 f([a_1, \dots, a_i])，考虑转移。因为每个子段的代价一定是 1, 2, 3 中的一个，所以我们可以通过双指针维护 lft_{i, j} = k (j \in \{1, 2, 3\})，表示 a_k 是 a 中第一个满足 \lceil \frac{a_i}{a_k} \rceil \le j 的元素。那么有转移 dp_i = \min_{j = 1}^3 dp_{lft_{i, j} - 1} + j。于是 D1 就做完了。

时间复杂度 O(n)。

Submission

:::

:::info[性质三]{open}

根据性质一，我们可以认为 a 单调递增。考虑对 a 贪心构造出一种较优的方案。一个自然的想法是要求每一个子段的花费 \le 2 且总子段数量尽量少。这样，对于子段 [a_l, \dots, a_r]，一定有 \lceil \frac{a_r}{a_{l - 1}} \rceil \gt 2。这意味着最多只有 \log a_n 个子段，那么 f(a) 的上限就是 2\log a_n = 2\log V \approx \textbf{120}。

:::

:::info[性质四]{open}

考虑 D2 的暴力 DP。容易想到设 dp_{l, r} 表示 f([a_l, \dots, a_r])。若我们固定 l，那么我们可以通过单调栈维护 [a_l, \dots, a_r] 中是后缀最小值的元素，而 lft_{i, j} 可以通过二分求出。时间复杂度 O(n^2 \log n)。

一个显然的性质是，对于固定的 r，dp_{l, r} 单调递减。

:::

:::success[D2 做法]{open}

性质三说明，dp_{l, r} 的值域较小；性质四说明，dp_{l, r} 数组在固定 r 时具有单调性。于是我们可以利用一个经典 trick：交换 DP 的下标与值。

设 dp'_{r, w} 表示最小的 l 使得 f([a_l, \dots, a_r]) \le w。那么转移是显然的：dp'_{r, w} = \min_{j = 1}^3 dp'_{lft_{r, j} - 1, w - j}。特别地，令 dp'_{r, 0} = r + 1。初始状态是 dp'_{0, w} = 1。

考虑如何统计答案。容易发现，\forall l \in [dp'_{r, w}, dp'_{r, w - 1}), dp_{l, r} = w，根据这一点统计即可。需要注意的是，因为 DP 是在单调栈上进行的，所以使用的下标均为单调栈的下标，要计算实际的下标还需要稍作转换，详见代码实现。

时间复杂度 O(n \log n + n \log V)。

Submission

:::