我看这里没有 multiset 的做法,来加一个
题意:
位置 iii 能跳到 位置 [i+l,i+r][i + l, i + r][i+l,i+r] 的位置,跳到了 iii 位置后能获得 arriarr_iarri 的能量,i>Ni > Ni>N 算完成,使总能量最大
解法:
换句话来说,位置 iii 从位置 [i−r,i−l][i - r, i - l][i−r,i−l] 的位置跳来
显然 dp ,
dpi=maxi−r≤j≤i−ldpj+arridp_i = max_{i - r \le j \le i-l}{dp_j} + arr_i dpi =maxi−r≤j≤i−l dpj +arri
这个时候,就可以使用 multiset 来解决
分为 3 种操作:
1. 添加 dpi−ldp_{i - l}dpi−l
2. 删除 dpi−r−1dp_{i - r - 1}dpi−r−1
3. 查询集合最大值
STL真香