ChatGPT教你算法竞赛·单调队列优化DP

ChatGPT编程1年前 (2023)发布 一起用AI
522 0 0

本文几乎都是由ChatGPT生成,包括后面的例题的题解。

代码是我根据题解自己实现的。

几天的使用下来,我发现ChatGPT是一个强力的算法竞赛的好帮手,所以有了这篇文章作为试水。

单调队列是什么?

单调队列是一种数据结构,它是一个具有单调性的队列。这意味着队列中的元素必须满足某种单调性,比如单调递增或单调递减。单调队列可以用来解决许多不同的问题,包括求最大值、最小值和优化算法的时间复杂度。

如何用单调队列求滑动窗口最大值

单调队列可以用来求解滑动窗口问题,其中窗口内的最大值是我们感兴趣的。在滑动窗口中,我们不断地将新的元素添加到队列的末尾,并将队列的头部元素删除,使得窗口的大小保持不变。

求滑动窗口最大值的关键在于如何维护队列中的元素的单调性。在这种情况下,我们可以使用一个单调递减的队列,这意味着队列中的元素是按照从大到小的顺序排列的。在添加新元素时,我们会把它与队列中所有比它小的元素都删除,然后再将它添加到队列的末尾。这样,队列中始终保持着一组单调递减的元素,其中第一个元素就是当前窗口中的最大值。

假设我们有一个数组 A = [3, 4, 2, 5, 1, 6],。

当第一个元素(A[0] = 3)被添加到窗口中时,队列中只有一个元素,即 3。

当第二个元素(A[1] = 4)被添加到窗口中时,此时,我们比较 4 和队列中末尾的元素, 很明显比3大,因此队列中的元素变为 [4]。

当第三个元素(A[2] = 2)被添加到窗口中时,此时,我们比较 2 和队列中末尾的元素,发现 2 比 4 小,所以不会删除 4,队列中的元素变为 [4, 2]。

当第四个元素(A[3] = 5)被添加到窗口中时,。此时,我们比较 5 和队列中末尾的元素,发现 5 比 4 和 2都 大,所以会连续删除 4 和 2。队列中的元素变为 [5]

继续按照这种方式,我们可以计算出整个滑动窗口的最大值序列为 [4, 5, 5, 6],

注意:因为滑动窗口的大小不超过 3,因此在具体的实现中,我们在每一步开始前,比较队头元素与当前元素的距离是否已经超出窗口了,如果已经超过,则需要踢掉队头元素。具体可以看代码实现。

这样,我们就可以利用单调队列来求解滑动窗口最大值问题,这样的时间复杂度为 O(n),其中 n 是数组 A 的长度。

代码实现(Python / C++)

from collections import deque

def max_in_sliding_window(nums, k):
if not nums:
return []

result = []
window = deque()
for i, num in enumerate(nums):
# 移除队列中小于当前值的元素
while window and nums[window[1]] < num:
window.pop()
# 移除队列中窗口已经滑出的元素
if window and i window[0] >= k:
window.popleft()
# 将当前值加入队列
window.append(i)
# 将当前窗口的最大值加入结果列表
if i >= k 1:
result.append(nums[window[0]])

return result

# 测试用例
nums = [1, 3, 1, 3, 5, 3, 6, 7]
k = 3
print(max_in_sliding_window(nums, k)) # 输出 [3, 3, 5, 5, 6, 7]

vector<int> max_in_sliding_window(vector<int>& nums, int k) {
if (nums.empty()) return {};

vector<int> result;
deque<int> window;
for (int i = 0; i < nums.size(); i++) {
// 移除队列中小于当前值的元素
while (!window.empty() && nums[window.back()] < nums[i]) {
window.pop_back();
}
// 移除队列中窗口已经滑出的元素
if (!window.empty() && i window.front() >= k) {
window.pop_front();
}
// 将当前值加入队列
window.push_back(i);
// 将当前窗口的最大值加入结果列表
if (i >= k 1) {
result.push_back(nums[window.front()]);
}
}

return result;
}

int main() {
// 测试用例
vector<int> nums = {1, 3, 1, 3, 5, 3, 6, 7};
int k = 3;
vector<int> result = max_in_sliding_window(nums, k);
for (int num : result) {
cout << num << ” “;
} // 输出 3 3 5 5 6 7
}

P1725 琪露诺

题目描述

在幻想乡,琪露诺是以笨蛋闻名的冰之妖精。

某一天,琪露诺又在玩速冻青蛙,就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多,在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。

小河可以看作一列格子依次编号为 00NN,琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动,当她在格子 ii 时,她只移动到区间 [i+L,i+R][i+L,i+R]中的任意一格。你问为什么她这么移动,这还不简单,因为她是笨蛋啊。

每一个格子都有一个冰冻指数 AiA_i,编号为 00 的格子冰冻指数为 00。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 AiA_i。琪露诺希望能够在到达对岸时,获取最大的冰冻指数,这样她才能狠狠地教训那只青蛙。

但是由于她实在是太笨了,所以她决定拜托你帮它决定怎样前进。

开始时,琪露诺在编号 00 的格子上,只要她下一步的位置编号大于 NN 就算到达对岸。

输入格式

第一行三个正整数 N,L,RN, L, R

第二行共 N+1N+1 个整数,第 ii 个数表示编号为 i−1i-1 的格子的冰冻指数 Ai−1A_{i-1}

输出格式

一个整数,表示最大冰冻指数。

样例 #1

样例输入 #1

5 2 3
0 12 3 11 7 -2

样例输出 #1

11

提示

对于 60%60\% 的数据,N≤104N \le 10^4

对于 100%100\% 的数据,N≤2×105N \le 2\times 10^5−103≤Ai≤103-10^3 \le A_i\le 10^3 1≤L≤R≤N1 \le L \le R \le N 。数据保证最终答案不超过 231−12^{31}-1

思路

一种可能的解决方案是使用动态规划。

我们可以定义状态 f[i]f[i] 表示到达位置 ii 时可以获得的最大价值和。

然后我们可以通过以下方式转移状态:

f[i]=max(f[j]+A[i])(i−R≤j≤i−L)f[i] = \max(f[j] + A[i]) \quad (i – R \leq j \leq i – L)

这意味着如果我们在位置 ii 处,我们可以查看位置 [i−R,i−L][i – R, i – L] 中的所有位置 jj,并选择使f[i]f[i] 最大的位置。

我们可以使用一个循环枚举位置 ii,然后使用一个循环枚举位置 jj,并计算 f[i]f[i] 的值。

这是一种可能的解决方案,但是它有一个缺点,即时间复杂度为 O(N2)O(N^2)

另一种可能的解决方案是优化上述算法,将时间复杂度降低到 O(N)O(N)

我们可以使用一个单调队列来维护 f[j]f[j] 的值。单调队列可以在每次计算 f[i]f[i] 时让我们快速找到 [i−R,i−L][i – R, i – L] 中的最大值。

首先我们枚举位置 ii,然后将 f[j]f[j] 的值添加到单调队列中。每次添加一个新值时,我们需要从队列中删除所有小于等于当前值的值,以维护队列的单调性。

然后,当计算 f[i]f[i] 时,我们可以查看队列的队首元素,它是队列中的最大值。我们可以将它与 f[i]f[i] 相加,并将结果存储在 f[i]f[i] 中。

同时,我们需要从队列中删除所有下标小于 i−Ri – R的元素,以维护队列的长度。

显然我们可以在枚举到 N”>i+R>Ni + R > N 的时候,计算结果,即 N)”>ans=max(f[i])(i+R>N)ans = max(f[i]) (i + R > N)

该算法的时间复杂度为O(N)O(N),因为每个位置 ii 只会被枚举一次,并且每次操作都只需要 O(1)O(1) 的时间。

总的来说,这是一种有效的优化方法,可以将算法的时间复杂度从 O(N2)O(N^2) 降低到 O(N)O(N)

void solve() {
int N, L, R;
std::cin >> N >> L >> R;
std::vector<int> a(N + 1);
for (int& x : a) std::cin >> x;
const int inf = 2e9;
std::vector<int> dp(N + 1, inf);
std::deque<int> dq;
dp[0] = 0;
int res = inf;
for (int i = L; i <= N; i++) {
int right_bound = i L, left_bound = i R;
while (!dq.empty() && dp[dq.back()] <= dp[right_bound]) dq.pop_back();
dq.push_back(right_bound);
while (!dq.empty() && dq.front() < left_bound) dq.pop_front();
dp[i] = dp[dq.front()] + a[i];
if (i + R > N) res = std::max(res, dp[i]);
}
std::cout << res << \n;
}

© 版权声明

相关文章