洛谷 P3957 分析（别看）

科技起源

2026-07-08 16:22:25

发布于：河北

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：有一个格子的数目 $n$ 和 $n$ 个格子的序列，每到达一个位置，就可以获得格子对应的分数，改进前机器人弹跳的固定距离 $d$ ，以及希望至少获得的分数 $k$
允许：将机器人改造，花费 $g$ 元改造后将会使跳跃距离增加 $g$ ，求到任意一个位置时可以获得至少 $k$ 分的最小 $g$ 是多少
禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n \le 5 \times10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一个序列，初始有一个机器人的固定跳跃距离 $d$ 。可以将机器人改造，花费 $g$ 元改造后将会使跳跃距离增加 $g$ ，求到任意一个位置时可以获得至少 $k$ 分的最小 $g$ 是多少

2 题目破题推导（明显是道线性dp，主要看模型匹配部分）

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 分情况考虑

2.4 数学

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：时刻求取最小值 $\longrightarrow$ $\huge{线性动态规划}$

3.1 需要注意的点

优化：朴素dp需要 $O(n^2)$ ，因为这题如果 $O(n~log~n^2)$ 会超时
因为这题将 dp[i] 定义为以 $i$ 为结尾时最长长度
因为dp[i]需要前面最大的dp[j]，而dp又是具有单调性的
因此考虑用单调队列优化

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long 

int n, d, k;
const int N = 5e5 + 10;
int x[N], a[N];
int dp[N];
int q[N];
bool check(int g){
	memset(dp, -127, sizeof(dp));
	memset(q, 0, sizeof(q));
	int mn = max(1LL, d - g), mx = d + g;
	int head = 1, tail = 0, j = 0;
	dp[0] = 0;
	for (int i = 1;i <= n;i++){
		while(x[i] - x[j] >= mn && j < i){
			if (dp[j] > -99999999){
				while(dp[q[tail]] <= dp[j] && head <= tail){
					tail--;
				}
				q[++tail] = j;
			}
			j++;
		}
		while(x[i] - x[q[head]] > mx && head <= tail){
			head++;
		}
		if (head <= tail){
			dp[i] = dp[q[head]] + a[i];
		}
		if (dp[i] >= k){
			return true;
		}
	}
	return false;
}

signed main(){
	
	cin >> n >> d >> k;
	for (int i = 1;i <= n;i++){
		cin >> x[i] >> a[i];
	}
	int l = 0, r = N;
	int ans = -1;
	while(l < r){
		int mid = (l + r) / 2;
		if (check(mid)){
			r = mid;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans;
	
	return 0;
}