检查一下单调队列弹出队首的边界有没有写错,参考下列代码:
for (int i = l; i <= n; i++) {
while(q.size() && dp[q.back()] <= dp[i - l]) q.pop_back();
while(q.size() && (i - l) - q.front() > (r - l)) q.pop_front();
q.push_back(i - l);
dp[i] = dp[q.front()] + a[i];
if(i + r > n) ans = max(ans, dp[i]);
}
for (int i = l; i <= n; i++) {
while(q.size() && dp[q.back()] <= dp[i - l]) q.pop_back();
while(q.size() && (i - l) - q.front() > (r - l + 1)) q.pop_front();
q.push_back(i - l);
dp[i] = dp[q.front()] + a[i];
if(i + r > n) ans = max(ans, dp[i]);
}
不得不说 hack 真挺强的。