#O1051. 跳格子
跳格子
题目描述
一条长度为 的格子路,第 格有一个分数 (可为负)。从第 格出发,每次可以前进 格,最终必须落在第 格。总得分为经过的格子(含第 格,不含第 格)分数之和。求最大总得分。
题目类型
动态规划、单调队列优化
输入格式
第一行两个整数 。
第二行 个整数 。
输出格式
一行一个整数,表示最大总得分。
样例 #1
样例输入 #1
6 3
1 -2 3 -1 2 5
样例输出 #1
11
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 格子数 | |
| 单次最大步长 | |
| 分数 |
- ,用单调队列维护滑动窗口最大值,答案用
long long。