单调队列+dp
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
int n=nums.size();
int f[n];
f[0]=nums[0];
deque<int>q;
q.push_back(0);
for(int i=1;i<n;i++){
if(q.front()<i-k)q.pop_front();
f[i]=f[q.front()]+nums[i];
while(q.size() && f[q.back()]<=f[i])q.pop_back();
q.push_back(i);
}
return f[n-1];
}
};
5631. 跳跃游戏 VI[https://leetcode-cn.com/problems/jump-game-...
单调队列DP HDU5945题意给定整数，存在如下两种操作。1.2.如果 求让变为的最小操作次数。题解状态定义：表...
给出一个非负整数数组，你最初定位在数组的第一个位置。 数组中的每个元素代表你在那个位置可以跳跃的最大长度。 判断你...
题目：洛谷P5858 「SWTR-03」Golden Sword[https://www.luogu.com.cn...
1.题目相关 标签：DP 单调队列优化 题目地址：http://poj.org/problem?id=1821 题...
1.题目相关 标签：DP 单调队列优化 题目地址：不是VIP没法看。。。。 题目大意：给定N和K，表示有N个数，在...
链接如下: 跳跃游戏二 - 题库 - 计蒜客 这是上一个条约游戏的延伸.看到这题第一个想法是把所有情况列出来,但是...
队列中各元素序列是严格单调递增或递减的，队首和队尾都可以出队，但入队只能从队尾入队。由于队列内元素有序，取最值的复...
42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。...
原题链接[https://www.acwing.com/problem/content/137/] 给定一个长度为...
本文标题：5631. 跳跃游戏 VI（单调队列+dp）
本文链接：https://www.haomeiwen.com/subject/dtkknktx.html
网友评论