P1725 琪露诺 题解

洛谷博客链接：https://www.luogu.com.cn/article/jelykwpn

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

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

设 $d{p}_i$ 为到达第 $i$ 个格子所获得的最大冰冻指数，初始 $d{p}_0$ 为 $0$，$d{p}_1\sim d{p}_n$ 为负无穷。

由于第 $i$ 个格子可以跳到 $i+l\sim i+r$ 个格子，所以 $d{p}_i$ 可以由 $d{p}_{i-r}\sim d{p}_{i-l}$ 转移而来。易得转移：$d{p}_i=\underset{j=i-r}{\overset{i-l}{\max }}d{p}_j+a_i$。

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

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

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

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

一些注意事项：

• $d{p}_i$ 有可能出现相同的，因此我开的是 multiset。
• 删去 $d{p}_{i-r-1}$ 时，应写作 s.erase (s.find (dp[i - r - 1]))。
• 统计答案应从 $d{p}_{n-r+1}\sim d{p}_n$ 中取最大值。
• set 中最大值为 *s.rbegin ()。

代码：

#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;
}