题解：CF2159D1 Inverse Minimum Partition (Easy Version)

· · 题解

首先，本题很容易得出一个暴力 dp O(n^{2}) 的做法：dp_{i} = \min\limits_{j=0}^{i-1}{dp_{j} + \operatorname{cost}([a_{j+1},a_{j+2},\dots,a_{i}])}。但显然这不够优秀。

接下来介绍两个神奇的结论。只需了解任意一条就可以解决 D1，但是只有将这两条都掌握才能解决 D2。

（备注：下文称 a 的最大取值为 V）

:::info[D1 解法 1（性质 1）]

f(a) \leq 2 \log_{2} a_{n}

考虑一种每个子段的 \operatorname{cost} 都为 1 或 2 的贪心做法。因为你在划分时根据贪心策略显然会将第一个 < \frac{a_{n}}{2} 的数划为下一段的右端点，所以不难发现 \operatorname{cost} = 2 的子段数量显然不超过 \log_{2} a_{n} 个。

这样答案范围直接缩小到了 128 以内。我们可以设置一个 r_{i} 维护 f([a_{1},a_{2},\dots,a_{k}]) \leq i 的最大 k 值，省去原暴力做法中许多不必要的转移，实现 O(n \log_{2} V) 的 dp。 :::

:::info[D1 解法 2（性质 2）] 存在一种最优解，使得划分出的每一个子段的 \operatorname{cost} 值 \leq 3。这是因为，对于任意一个 \operatorname{cost} 值 = x (x \geq 4) 的子段都可以拆成一个 \operatorname{cost} 值 \leq \frac{x}{2} 的子段和一个 \operatorname{cost} 值 \leq 2 的子段。由于 \frac{x}{2} + 2 \leq x，这样做显然是不劣的。

这样，就可以考虑使用数据结构解决 D1 了，但相对于解法 1 而言比较繁琐，不再介绍。 :::

:::info[D2 解法] 模仿 D1 解法 1，我们将 dp_{i,j} 的定义修改为使得 f([a_{k},a_{k+1},\dots,a_{j}]) \leq i 的最小 k。显然，dp_{0,j} = j+1。

当 i = 1,2,3 时，dp_{i,j} 可以通过使用线段树计算出来。

根据上述两条性质可知对于 \forall i \geq 4, dp_{i,j} = \min\limits_{k=1}^{3}(\min\limits_{l=\max(dp_{i,j-k}-1,0)}^{j-1}dp_{l,k})。对 i = 1,2,3 时的 dp_{i,j} 分别开一个 ST 表实现 O(1) 查询区间查询最小值即可。

答案即为 \sum\limits_{i=1}^{128} \sum\limits_{j=1}^{n} i(dp_{i,j} - dp_{i-1,j})。时间复杂度 O(n (\log_{2} n + \log_{2} V))。 :::

AC Code