#P3264. 跳格子(200分)
-
1000ms
Tried: 174
Accepted: 30
Difficulty: 5
所属公司 :
华为od
跳格子(200分)
思路:单调队列优化的动态规划
根据题目意思,我们可以想到一种很简单的动态规划方法:从左到右dp,对于每一个i , 去看[i−k,i−1] 这个下标范围内的最大可能的dp值,假设是x , 那么就是dp[i]=x+a[i]
这样复杂度是O(nk)的不能拿满分,所以先学习一下下面两个算法:
先学习一下单调队列
在学习下单调队列优化动态规划
我们可以使用单调队列来维护[i−k,i−1] 内的dp最大值。 复杂度为O(n)
C++
#include <iostream>
#include <deque>
using namespace std;
int getAns(int arr[], int n, int k) {
deque<pair<int, int>> q;
int dp[n];
dp[0] = arr[0];
q.push_back(make_pair(0, dp[0]));
for (int i = 1; i < n; i++) {
// 移除窗口范围之外的元素
while (!q.empty() && q.front().first < i - k) {
q.pop_front();
}
// 计算dp[i],取队列中的最大值加上当前元素的值
dp[i] = arr[i] + q.front().second;
// 移除队列中小于等于dp[i]的元素
while (!q.empty() && q.back().second <= dp[i]) {
q.pop_back();
}
// 将当前dp[i]加入队列中
q.push_back(make_pair(i, dp[i]));
}
return dp[n - 1];
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int k;
cin >> k;
cout << getAns(arr, n, k) << endl;
return 0;
}
Java
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
// 读取输入数组
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int k = sc.nextInt();
System.out.println(getAns(arr, n, k));
return;
}
// 获取最终结果
public static int getAns(int[] arr, int n, int k) {
Queue<Integer[]> q = new LinkedList<>();
int[] dp = new int[n];
dp[0] = arr[0];
q.add(new Integer[]{0, dp[0]});
for (int i = 1; i < n; i++) {
// 移除超出窗口范围的元素
while (!q.isEmpty() && q.peek()[0] < i - k) {
q.poll();
}
// 计算dp[i],取队列中的最大值+当前元素的值
dp[i] = arr[i] + q.peek()[1];
// 移除队列中小于等于dp[i]的元素
while (!q.isEmpty() && q.peek()[1] <= dp[i]) {
q.poll();
}
// 将当前dp[i]加入队列中
q.add(new Integer[]{i, dp[i]});
}
return dp[n - 1];
}
}
Python
from collections import deque
def get_ans(arr, n, k):
q = deque()
dp = [0] * n
dp[0] = arr[0]
q.append((0, dp[0]))
for i in range(1, n):
# 移除窗口范围之外的元素
while q and q[0][0] < i - k:
q.popleft()
# 计算dp[i],取队列中的最大值加上当前元素的值
dp[i] = arr[i] + q[0][1]
# 移除队列中小于等于dp[i]的元素
while q and q[-1][1] <= dp[i]:
q.pop()
# 将当前dp[i]加入队列中
q.append((i, dp[i]))
return dp[-1]
n = int(input())
arr = list(map(int, input().split()))
k = int(input())
print(get_ans(arr, n, k))
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
input += data;
});
process.stdin.on('end', () => {
const lines = input.trim().split('\n');
const n = parseInt(lines[0]);
const arr = lines[1].split(' ').map(Number);
const k = parseInt(lines[2]);
console.log(getAns(arr, n, k));
});
function getAns(arr, n, k) {
const q = [];
const dp = new Array(n).fill(0);
dp[0] = arr[0];
q.push([0, dp[0]]);
for (let i = 1; i < n; i++) {
// 移除窗口范围之外的元素
while (q.length > 0 && q[0][0] < i - k) {
q.shift();
}
// 计算dp[i],取队列中的最大值加上当前元素的值
dp[i] = arr[i] + q[0][1];
// 移除队列中小于等于dp[i]的元素
while (q.length > 0 && q[q.length - 1][1] <= dp[i]) {
q.pop();
}
// 将当前dp[i]加入队列中
q.push([i, dp[i]]);
}
return dp[n - 1];
}
题目描述
小明和朋友们一起玩跳格子游戏,每个格子上有特定的分数score[] =[1 -1-6 7 -17 7],从起点score[0开始,每次最大的步长为k,请你返回小明跳到终点score[n-1]时,能得到的最大得分。
注:
格子的总长度和步长的区间在[1,100000]
每个格子的分数在[-10000,10000]区间中
输入描述
6 //第一行输入总的格子数量
1 -1 -6 7 -17 7/第二行输入每个格子的分数score[]
2 //第三行输入最大跳的步长k
样例1
输入
6
1 -1 -6 7 -17 7
2
输出
14