==========以上是题目====
考虑到2e5的数据范围,暴力的先枚举i,在枚举走的步数区间j,是过不了的,
我们可以看出对于每一个i,只需要找出能走的i的区间的dp最大值即可,求区间最大值可以使用单调队列,时间复杂度就是O(n)的
注意:a[]有负数,所以要把dp[]和ans都初始化为负数
const int N = 2e5 + 10;LL n,L,R;
LL dp[N],a[N],dq[N];
int hh = 1,tt = 0;void solve()
{cin >> n >> L >> R;for (int i = 0;i <= n;i ++) cin >> a[i];LL ans = -inf;memset(dp,-0x3f,sizeof dp);dp[0] = 0;for (int i = L;i <= n;i ++){while(hh <= tt && dq[hh] < i - R) hh ++;//队头合法性while(hh <= tt && dp[dq[tt]] < dp[i - L]) tt --;//队尾dp值<距离i最近的dp值dq[++tt] = i - L;dp[i] = dp[dq[hh]] + a[i];//队头最优if (i + R > n) //如果能过桥就更新ansans = max(ans,dp[i]);}cout << ans << endl;}