单调栈和单调队列优化DP
单调栈和单调队列优化DP
luogu P1725 琪露诺
一道比较板的题
明显是一个DP，则有
\[{dp}_i=\max_{j=i-r}^{i-l}dp_j + a_i
\]
如果暴力则为 \(O(n^2)\)
但是发现 \(\max_{j=i-r}^{i-l}dp_j\) 就是单调队列所解决的问题，所以直接单调队列维护即可
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 2e5 + 5;
int n, l, r;
ll a[N], dp[N];
deque<int> q;
int main() {
// FASTIO;
cin >> n >> l >> r;
memset(dp, 128, sizeof dp);
for (int i = 0; i <= n; i++) {
cin >> a[i];
// if (i <= l - 1) dp[i] = a[i];
}
dp[0] = a[0];
q.push_back(0);
ll ans = -1e9 - 7;
for (int i = l; i <= n; i++) {
while (!q.empty() && dp[q.back()] < dp[i - l]) q.pop_back();
q.push_back(i - l);
while (q.front() + r < i) q.pop_front();
if (q.size()) dp[i] = dp[q.front()] + a[i];
if (i + r > n) ans = max(ans, dp[i]);
}
cout << ans;
return 0;
}