自动搬运

查看原文

来自洛谷，原作者为

	寻逍遥2006 晓看天色暮看云，行也思君，坐也思君；春赏百花冬赏雪，醒也思卿，梦也思卿

搬运于2025-08-24 23:10:30，当前版本为作者最后更新于2025-02-27 22:00:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

测试点 $1\sim 3$

直接搜索所有可能的解，由于 $n$ 很小可以直接通过。

测试点 $4\sim 10$

题目相当于对于每一个前缀，要将其分成若干个区间，要求区间和单调递减。同时字典序最小的限制要求后面的区间尽可能短，这个过程可以之间贪心。

直接 $O(n)$ 模拟这一个过程，总时间复杂度 $O(n^2)$。

测试点 $11\sim 17$

考虑记 $f_{i,j}$ 表示当前这一段是 $[i,j)$，处理 $[0,j)$ 一共要分多少组，同时用 $g_{i,j}$ 维护需要维护的求和。

因此有转移 $f_{i,j}=f_{k,i}+1$，$g_{i,j}=g_{k,i}+f_{i,j}i$，其中 $k$ 为最大的满足 $\sum\limits_{g=k}^{i-1}v_g>\sum\limits_{g=i}^{j-1}v_g$ 的数。

记 $sum_i=\sum\limits_{j=i}^nv_i$，对于 $f_{i,j}$ 而言的转移点就是最大的 $k$，满足 $sum_k-sum_i>sum_i-sum_j$，也就是 $sum_k>2sum_i-sum_j$。

最终就是要求所有 $f_{i,i+1}$ 和 $g_{i,i+1}$。但由于每一个点仅由一个点转移而来，所以考虑所有有用的状态数量。发现任何有用的状态都对应一个区间 $[i,j)$，其在某一个前缀的划分方案中出现。

对于 $i-j\le \sqrt{n}$ 区间，这样的区间一共只有 $O(n\sqrt{n})$ 个；对于 $i-j>\sqrt{n}$ 的区间，一个前缀中最多只有 $O(\sqrt{n})$ 个长度 $>\sqrt{n}$ 的组，所以最多只有 $O(n\sqrt{n})$ 个有用的区间。因此，有用的状态最多只有 $O(n\sqrt{n})$ 个。

直接使用记忆化搜索，这样会访问到的状态数就是 $O(n\sqrt{n})$ 的。现在的问题就变成如何找到转移的 $k$，对于每一个状态使用二分可以做到 $O(\log n)$。

总复杂度 $O(n\sqrt{n}\log n)$。

常数较大的可能只能通过前一部分。

满分做法

优化找到每一个状态转移的 $k$。

按照 $i$ 从大到小扫描，找到所有我们需要转移的 $j$。假设对于 $i$ 的所有 $j$ 已经按照从小到大排序了。

对序列进行分块，对于一个点 $i$，可以直接暴力 $O(\sqrt{n}+cnt)$ 扫描出所有 $k$ 和 $i$ 在同一个块内的 $j$ 对应的转移点，其中 $cnt$ 为满足这样条件的 $j$ 的数量。

对于 $k$ 与 $i$ 不在同一个块的转移，可以将当前块内的所有这样的状态 $(i,j)$ 按照 $2sum_i-sum_j$ 进行排序，然后 $O(n)$ 扫描一遍所有的 $k$，即可同时扫描所有的 $(i,j)$ 即可得到转移。由于 $sum_i$ 的值有上界 $n^2$，排序可以做到 $O(n)$。

对于一个点 $i$，如果所有的 $j$ 是从大到小加入的，就可以保证在处理 $i$ 时所有的 $j$ 已经排序完成，因此在对于每一个点加入需要转移的状态时，需要按照 $i$ 的大小从大到小加入。

最后直接按照 $i$ 从小到大依次求解 $f$ 和 $g$ 即可。

总时间复杂度 $O(n\sqrt{n})$。