如果你 HACK 全错
查看原帖
如果你 HACK 全错
693428
unDefined_Future楼主2023/10/13 14:23

检查一下单调队列弹出队首的边界有没有写错,参考下列代码:

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(); // AC
        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(); // WA on HACK
        q.push_back(i - l);
        dp[i] = dp[q.front()] + a[i];
        if(i + r > n) ans = max(ans, dp[i]);
    }

不得不说 hack 真挺强的。

2023/10/13 14:23
加载中...