P1725. 琪露诺

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 171 阅读时长 ≈ 1 分钟

考点

  • 线性动态规划
  • 单调队列

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 50;
int ans = 0xc0c0c0c0;
int n, l, r, head, tail, a[maxn], q[maxn], dp[maxn];

int main() {
  cin >> n >> l >> r;
  memset(dp, 0xc0, sizeof(dp)), dp[0] = 0;
  for (int i = 0; i <= n; ++i) cin >> a[i];
  for (int i = l; i <= n; ++i) {
    while (head < tail && i > r + q[head]) ++head;
    while (head < tail && dp[q[tail - 1]] < dp[i - l]) --tail;
    q[tail++] = i - l;
    dp[i] = dp[q[head]] + a[i];
    if (i + r > n) ans = max(ans, dp[i]);
  }
  cout << ans;
  return 0;
}

思路

根据题意，显然能得到状态转移方程： \[ dp\left[ i \right] =\max \left( dp\left[ j \right] \right) +a\left[ i \right] ,j\in \left[ i-R,i-L \right] \] 求区间极值，用单调队列优化即可。