题解

思路

长度为 $k,k-1,\ldots,1$ 的区间至少占用 $k(k+1)/2$ 个位置，所以只需考虑 $k=O(\sqrt n)$。

对固定长度 $k$，从右向左维护后缀中可行的 $k$ 段方案。令 $dp_k[i]$ 表示在后缀 $[i,n]$ 中选择长度依次为 $k,k-1,\ldots,1$ 的区间时，第一段区间和的最大可能值；不可行时为负无穷。

做法

当 $k=1$ 时，$dp_1[i]$ 是后缀最大元素。对 $k\ge2$，在位置 $i$ 有两种选择：

• 跳过 $a_i$，继承 $dp_k[i+1]$；
• 让长度为 $k$ 的第一段从 $i$ 开始。记该段和为 $S$，若 $S<dp_{k-1}[i+k]$，就能在其右侧接上合法的其余 $k-1$ 段，此时用 $S$ 更新答案。

因此

$$dp_k[i]=\max\left(dp_k[i+1],\;S(i,i+k-1)\ \text{（当 }S(i,i+k-1)<dp_{k-1}[i+k]\text{）}\right).$$

每一层只依赖上一层，使用两个一维数组即可。

子任务 1

正整数全等时，任意较长区间的和都严格大于较短区间的和，无法满足递增要求，所以答案恒为 $1$。

子任务 2

枚举 $k$ 并递归枚举所有区间起点，直接检查相邻区间和，适用于 $n\le14$。

子任务 3

可按定义枚举当前后缀中的第一段起点，得到 $O(n^2\sqrt n)$ 的转移。

子任务 4

利用后缀最大值递推消去起点枚举，得到上述满分算法。

正确性证明

对 $k$ 归纳。$k=1$ 时，后缀中任选一个单点即可，最大首段和显然是后缀最大值。假设 $dp_{k-1}$ 定义成立。任意后缀 $[i,n]$ 中的 $k$ 段方案，要么不使用位置 $i$，属于 $dp_k[i+1]$；要么第一段恰从 $i$ 开始，其余方案位于 $i+k$ 之后，且存在的充要条件是当前段和严格小于右侧 $(k-1)$ 段方案可取得的最大首段和。递推完整覆盖且只保留可行方案，因此成立。最终最大的可行层数即答案。

复杂度

• 时间复杂度：$O(n\sqrt n)$。
• 空间复杂度：$O(n)$。