题解：CF2159D1 Inverse Minimum Partition (Easy Version)

考虑一种每个子段的 $\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。

存在一种最优解，使得划分出的每一个子段的 $\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 而言比较繁琐，不再介绍。

模仿 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))$。