题解

我看这里没有 multiset 的做法，来加一个
题意：
位置 $i$ 能跳到 位置 $[i + l, i + r]$ 的位置，跳到了 $i$ 位置后能获得 $arr_i$ 的能量，$i > N$ 算完成，使总能量最大
解法：
换句话来说，位置 $i$ 从位置 $[i - r, i - l]$ 的位置跳来
显然 dp ,

$$dp_i = max_{i - r \le j \le i-l}{dp_j} + arr_i$$

这个时候，就可以使用 multiset 来解决
分为 3 种操作:

1. 添加 $dp_{i - l}$
2. 删除 $dp_{i - r - 1}$
3. 查询集合最大值

int main() {
	int N = read<int>(), l = read<int>(), r = read<int>();
	std:: vector<long long> arr(N + 1), dp(N + 1, -1e14); // 初始值负无穷大
	for (int i = 0; i <= N; ++i) arr[i] = read<int>(); // 注意这里要读入N + 1个数字

	std:: multiset<long long> st;
    dp[0] = 0; // 第一个值为 0

    long long res = -1e14;
	for (int i = l; i <= N; ++i) {
		// j in i - r, i - l max dp_j
		st.insert(dp[i - l]); // 插入

		if (i > r) { // 保证不越界
            auto it = st.find(dp[i - r - 1]);
            if (it != st.end()) st.erase(it); // 删除迭代器，删除值的话会把同样的值全部删了
        }

        dp[i] = *st.rbegin() + arr[i]; // *st.rbegin() 就是最大值了

        if (i + r > N) { // 如果下一步能跳到终点
            if (dp[i] > res) { // 并且结果比原来答案大
                res = dp[i]; // 更新答案
            }
        }
	}

	std:: cout << res << std:: endl;
}

STL真香