線上OJ：

一本通：http://ybt.ssoier.cn:8088/problem_show.php?pid=1417\

核心思想

首先、本題中提到 “ 至少 要花多少金幣改造機(jī)器人，能獲得 至少 k分 ”?？吹竭@樣的話語，基本可以考慮要使用 二分答案。
那么，本題中的 答案 是什么？就是: 在確定維修金幣g的情況下，能獲得的分?jǐn)?shù)是否會(huì)＞ k 。
由于本題中的 格子在同一條直線上，且只能從左往右跳，所以 每一種答案 都可以使用 動(dòng)態(tài)規(guī)劃 來解決。
而且動(dòng)態(tài)規(guī)劃的 dp 方程也很好找，因?yàn)?當(dāng)前格子的最高分 肯定是由 之前某個(gè)最高分的格子跳過來的，即：

$dp[i]=max(dp[i],dp[j]+a[i])$

所以，我們從 i 號格子前面的第一個(gè)格子開始查找得分最高的格子。在這里需要注意的是：不是所有的 j 都需要查找。只有當(dāng) j 的跳躍區(qū)間 [d-g, d+g] 能夠觸達(dá)（或包含）i坐標(biāo) 的時(shí)候，這個(gè) j 才能用于更新dp[i]。
以下三個(gè)舉例（及配圖）便于理解j和i的關(guān)系

舉例1： i 號格子位于坐標(biāo)10，j 號格子位于坐標(biāo)5（此時(shí) j 的跳躍區(qū)間為 [2,4]，也就是 j 能跳到的地方為[7,9]），所以此時(shí) j 號格子無法觸達(dá) i，所以 j 號格子不需要用于更新dp[i]。
舉例2： i 號格子位于坐標(biāo)10，j 號格子位于坐標(biāo)5（此時(shí) j 的跳躍區(qū)間為 [2,6]，也就是 j 能跳到的地方為[7,11]），所以此時(shí) j 號格子可以觸達(dá) i，所以 j 號格子需要用于更新dp[i]。
舉例3： i 號格子位于坐標(biāo)10，j 號格子位于坐標(biāo)5（此時(shí) j 的跳躍區(qū)間為 [6,8]，也就是 j 能跳到的地方為[11,13]），所以此時(shí) j 號格子無法觸達(dá) i，所以 j 號格子不需要用于更新dp[i]。

綜上所述，有效的 j 點(diǎn)應(yīng)該滿足
$d?g<=x[i]?x[j]<=d+g$，
我們令左邊界為 l = d - g，右邊界為 r = d + g，則僅當(dāng) 滿足①和②式的 j 點(diǎn) 才參與dp[i]的運(yùn)算

$x[i]?x[j]>=l$； ①
$x[i] - x[j] < =r $； ②

題解代碼：

解法一：二分答案 + 動(dòng)態(tài)規(guī)劃（僅80%分?jǐn)?shù)）

#include <bits/stdc++.h>
#define ll long long
#define MAXN 500005using namespace std;int n, d, k;ll x[MAXN], s[MAXN], dp[MAXN];// 檢查花費(fèi)g個(gè)金幣進(jìn)行改造后，最高得分是否會(huì)超過 k
bool check(int g)
{// 計(jì)算在花費(fèi)g金幣下，機(jī)器人每次向右跳的距離邊界[l, r] = [d-g, d+g]。注：左邊界不能小于1 int l = max(1, d - g);  // 機(jī)器人每次能跳躍的最小距離 int r = d + g;			// 機(jī)器人每次能跳躍的最大距離memset(dp, 0xaf, sizeof(dp));  // 全部初始化為一個(gè)很小的數(shù)。dp[0] = 0; // 數(shù)據(jù)即分?jǐn)?shù)都從第一個(gè)格子開始，所以第0個(gè)格子初始化為0分 for(int i = 1; i <= n; i ++){// 從i的前一個(gè)格子開始枚舉j，直到j(luò)枚舉到起點(diǎn)（如果i和j之間的距離已經(jīng)超過彈跳上限r(nóng)，則沒必要繼續(xù)j--了） for(int j = i - 1; (j >= 0) && (x[i] - x[j] <= r); j --){// 如果j號格子距離i號格子不能太近，至少要≥機(jī)器人彈跳的最小距離”,否則就j--，尋找更遠(yuǎn)的j if(x[i] - x[j] >= l){// i的最高得分應(yīng)該是從前面能跳過來的格子j里得分最高的格子跳過來的dp[i] = max(dp[i], dp[j] + s[i]);	if(dp[i] >= k) return true;}            }}return false;
}int main()
{scanf("%d%d%d", &n, &d, &k);for(int i = 1; i <= n; i ++)scanf("%lld%lld", &x[i], &s[i]);// 由于x[i]的坐標(biāo)范圍可到 10^9，在極端情況下有可能前面全是負(fù)值，只有最后一個(gè)x[n]是正值，此時(shí)要搜索的答案g也會(huì)達(dá)到 10^9（即一步跳到最后一個(gè)正值）。所以二分答案時(shí) r 應(yīng)取到 x[n]。但如此一來，效率就變低了，只能拿到80%的分?jǐn)?shù)int l = 0, r = x[n], mid, ans = -1;  while(l <= r){mid = (l + r) >> 1;if(check(mid)){ans = mid;r = mid - 1;}else l = mid + 1;}cout << ans << endl;return 0;
}

以上方法只能拿到80分，因?yàn)槎执鸢傅挠覅^(qū)間 r 取值為 x[n]，數(shù)據(jù)過于龐大。

解法二、二分答案 + 動(dòng)態(tài)規(guī)劃 + 單調(diào)隊(duì)列（100%）

由于 二分答案時(shí)的 r 取值為 x[n]過于龐大，所以此時(shí)考慮對 check 函數(shù)進(jìn)行優(yōu)化。由于 dp[i] 是之前的某個(gè)最大值 dp[j] 跳過來,所以可以考慮優(yōu)先隊(duì)列；同時(shí)由于 j 是有區(qū)間的，所以考慮優(yōu)先隊(duì)列的升級版–單調(diào)隊(duì)列（單調(diào)隊(duì)列適合在一個(gè)動(dòng)態(tài)小區(qū)間中尋找極值）

#include <bits/stdc++.h>
#define ll long long
#define MAXN 500005using namespace std;int n, d, k;ll x[MAXN], s[MAXN], dp[MAXN];//檢查花費(fèi)g個(gè)金幣進(jìn)行改造后，最高得分是否會(huì)超過k
bool check(int g)
{// 計(jì)算在花費(fèi)g金幣下，機(jī)器人每次向右跳的距離邊界[l, r] = [d-g, d+g]。注：左邊界不能小于1 ll l = max(1, d - g);  // 機(jī)器人每次向右跳的最小距離 ll r = d + g;			// 機(jī)器人每次向右跳的最大距離memset(dp, 0xaf, sizeof(dp));dp[0] = 0; // 數(shù)據(jù)即分?jǐn)?shù)都從第一個(gè)格子開始，所以第0個(gè)格子初始化為0分 ll j = 0;deque<int> q;for(int i = 1;i <= n;i ++){// 根據(jù)區(qū)間[l, r]，剔除隊(duì)尾的  while(x[i] - x[j] >= l)	// 根據(jù)i查找所有符合跳躍左邊界的j {// 將隊(duì)列中比 dp[j] 還小的直接移除 (由于按照單調(diào)隊(duì)列存儲，故從隊(duì)尾判斷)while( !q.empty() && dp[q.back()] < dp[j] )q.pop_back();q.push_back(j); // 把 j 放到單調(diào)隊(duì)列的尾部，此時(shí)dp[j]是當(dāng)前區(qū)間內(nèi)最小的 j ++;}// 根據(jù)區(qū)間 [l, r]，剔除隊(duì)頭的 while(!q.empty() && x[q.front()] + r < x[i]) // 如果最大的格子距離i太遠(yuǎn)，已經(jīng)超過彈跳上限r(nóng) q.pop_front();	// 則說對對頭元素不在 [l,r] 內(nèi)，彈出 if(!q.empty())	// 如果此時(shí)隊(duì)列依然非空，則取隊(duì)首的元素下標(biāo) q.front() 來做 dp dp[i] = dp[q.front()] + s[i];if(dp[i] >= k)return true;}return false;
}int main()
{scanf("%d%d%d", &n, &d, &k);for(int i = 1; i <= n; i ++)scanf("%lld%lld", &x[i], &s[i]);int l = 0, r = x[n], mid, ans = -1;while(l <= r){mid = (l + r) >> 1;if(check(mid)){ans = mid;r = mid - 1;}else l = mid + 1;}cout << ans << endl;return 0;
}

備注：這道題想 混分 有點(diǎn) 難，雖然參考輸入樣例2中給出了輸出 -1 的場景（即：所有正的分?jǐn)?shù)總和依然達(dá)不到目標(biāo)分?jǐn)?shù)k），但是實(shí)際的測試數(shù)據(jù)中并沒有這種情況，所以這道題騙分騙不到。