#O1051. 跳格子

跳格子

题目描述

一条长度为 nn 的格子路,第 ii 格有一个分数 aia_i(可为负)。从第 00 格出发,每次可以前进 1∼L1 \sim L 格,最终必须落在第 nn 格。总得分为经过的格子(含第 nn 格,不含第 00 格)分数之和。求最大总得分。

题目类型

动态规划、单调队列优化

输入格式

第一行两个整数 n,Ln, L。

第二行 nn 个整数 aia_i。

输出格式

一行一个整数,表示最大总得分。

样例 #1

样例输入 #1

6 3
1 -2 3 -1 2 5

样例输出 #1

11

数据规模与约定

数据范围 说明
1≤n≤1061 \le n \le 10^6 格子数
1≤L≤n1 \le L \le n 单次最大步长
−109≤ai≤109-10^9 \le a_i \le 10^9 分数
  • fi=ai+max⁡i−L≤j<ifjf_i = a_i + \max\limits_{i-L \le j < i} f_j,用单调队列维护滑动窗口最大值,答案用 long long。