题解

思路

因为所有元素均为正数，对一个固定区间求 $f$ 时，最优策略一定是从左向右让当前段尽量长。

做法

对每个位置 $i$，令 $p_i$ 为最小的、使 $A_i+A_{i+1}+\cdots+A_{p_i}>S$ 的位置；若不存在则令 $p_i=N+1$。再令 $dp_i=\sum_{r=i}^{N}f(A[i,r])$。当 $r<p_i$ 时整个区间只需一段；当 $r\ge p_i$ 时，第一段必为 $[i,p_i-1]$，余下部分等价于从 $p_i$ 开始。因此有 $dp_i=dp_{p_i}+N+1-i$。

从右向左计算 $dp$ 即可。由于元素为正，随着左端点右移，满足区间和不超过 $S$ 的最大右端点也只会右移，所以用双指针在线性时间内求出全部 $p_i$。

复杂度

最后累加所有 $dp_i$，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。