【CCC2019】 Tourism

题目大意

将一个长度为 $n$ 的序列分为 $\lceil \dfrac{n}{k}\rceil$ 段且每一段的长度不超过 $k$，求每一段的最大值的和。

数据范围满足，$1\le k\le n\le 10^6$。

思路

考虑暴力的 dp，定义 $f_{i,j}$ 表示前 $i$ 个分成 $j$ 段的答案。

$f_{i,j}=\max\limits_{l=i-k}^{i-1}(f_{l,j-1}+\max\limits_{r=l+1}^{i}(a_r))$

考虑如何优化这个 dp，显然枚举过程已经是最优，只能从状态上简化。

可以发现这样一个事实，我们之前枚举的大部分状态对于最终的答案都是没有贡献的。借此，我们发现对于 $i$，只有 $f_{i,\left \lceil \frac{i}{k} \right \rceil }$ 对之后的答案有贡献。证明如下：

• 若 $j<\left \lceil \frac{i}{k} \right \rceil$，那么必定有一段长度大于 $k$。
• 若 $j>\left \lceil \frac{i}{k} \right \rceil$，由上分析可知后面最少也要 $\left \lceil \frac{n-i}{k} \right \rceil$ 段，所以有 $j+\left \lceil \frac{n-i}{k} \right \rceil >\left \lceil \frac{i}{k} \right \rceil + \left \lceil \frac{n-i}{k} \right \rceil \geqslant \left \lceil \frac{n}{k} \right \rceil$ 一定不满足。

所以记 $g_i=f_{i,\left \lceil \frac{i}{k} \right \rceil }$，根据如上的方程，能够向 $g_i$ 贡献的只有满足 $i-k\leqslant j \leqslant i-1$ 且 $\left \lceil \frac{i}{k} \right \rceil-1=\left \lceil \frac{j}{k} \right \rceil$ 的 $j$，所以方程为：

$g_{i}=\max _{j=i-k}^{k \times\left\lfloor\frac{i-1}{k}\right\rfloor}\left(g_{j}+\max _{k=j+1}^{i} a_{k}\right)$

对于 $\max _{k=j+1}^{i} a_{k}$ 考虑使用单调栈进行求解，对于 $g_i$ 的区间最大值使用线段树维护，其时间复杂度为 $O(n\log n)$。

记录详情 - 洛谷 | 计算机科学教育新生态 - luogu.com.cn