P6647 题解 最后更新于 2025-05-02 00:00:52

## 题意 给定 $n$ 个景点的吸引度 $a_i$ 和 $k$ ，其中 $k$ 表示每天最多游览的景点数。需要按顺序浏览 $1-n$ 的景点，每天的评分是当天所有景点 $a_i$ 的最大值，求出当天数最少时评分之和的最大值。 $n,k\le 10^6$ ## 思路 设 $dp_i$ 为用最少的天数游览前 $i$ 个景点获得的最大评分。不难发现要使天数最少，能从前面转移过来的区间是可以直接求出的，为 $[i-k,\lfloor \frac{i-1}{k}\rfloor \times k ]$ 。 知道转移区间后问题转化为求 $\max{\{dp_j +\mathop{max}\limits_{j=i-k}^{\lfloor \frac{i-1}{k}\rfloor \times k ]}\}}$ 。 这玩意显然可以用线段树维护。更新 $\max{\{a_i\}}$ 的话用单调栈就能做。时间复杂度 $O(n \log n)$ 。