题解：P1725 琪露诺

· · 题解

温馨提示：这是一篇使用 set 优化 DP 的题解。

背景：前段有一场 ABC 的 D 题，如果使用 set 便可以很快地通过，但是身边的人有写 ST 表的，有写单调队列的，甚至还有写线段树的。再次拿到这道被称为单调队列优化 DP 的板子，我脑海中第一个出现的竟是使用 set 优化，于是便诞生了这篇题解。

设 dp_i 为到达第 i 个格子所获得的最大冰冻指数，初始 dp_0 为 0，dp_1\sim dp_n 为负无穷。

由于第 i 个格子可以跳到 i+l\sim i+r 个格子，所以 dp_i 可以由 dp_{i-r}\sim dp_{i-l} 转移而来。易得转移：dp_i=\max\limits_{j=i-r}^{i-l}dp_j+a_i。

显然上面转移是 O(n^2) 的，考虑如何优化。发现 dp_{i} 由 dp_{i-r}\sim dp_{i-l} 转移而来，dp_{i+1} 由 dp_{i-r-1}\sim dp_{i-l-1} 转移而来，有关区间只向右移动了一位，且我们只关心有关区间的最大值。

考虑用 set 维护有关区间，枚举到 i 时，set 维护的便是 dp_{i-r}\sim dp_{i-l} 这些值，从 set 中取最大值进行转移即可。

枚举到 i 时，在 set 中加入 dp_{i-l}，删去 dp_{i-r-1}。单次操作时间复杂度为 O(\log n)。

总时间复杂度为 O(n\log n)。虽然没有单调队列 O(n) 优秀，但比单调队列更加好写，且仍能轻松通过本题。

一些注意事项：

代码：

#include <bits/stdc++.h>
#define int long long
#define INF 1e9 
using namespace std;
typedef long long LL;

const int N = 1e6 + 10;
int n, l, r, ans = -INF;
int a[N], dp[N];
multiset <int> s;

signed main ()
{
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++) cin >> a[i];
    memset (dp, -0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = l; i <= n; i++) {
        if (i > r) s.erase (s.find (dp[i - r - 1]));
        s.insert (dp[i - l]); // 调整有关区间
        dp[i] = *s.rbegin () + a[i]; // 更新 dp 值
    }
    for (int i = n; i > n - r; i--) ans = max (ans, dp[i]); // 统计答案
    cout << ans;
    return 0;
}