首页 > 分享 > [NOIP2017 普及组]跳房子【题解】

[NOIP2017 普及组]跳房子【题解】

花匠小妙招
2026-01-06 17:05

题目背景

NOIP2017 普及组 T4

题目描述

跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下：

在地面上确定一个起点，然后在起点右侧画 nnn 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 ddd。小 R 希望改进他的机器人，如果他花 ggg 个金币改进他的机器人，那么他的机器人灵活性就能增加 ggg，但是需要注意的是，每次弹跳的距离至少为 111。具体而言，当 g<dg<dg<d 时，他的机器人每次可以选择向右弹跳的距离为 d−g,d−g+1,d−g+2,…,d+g−1,d+gd-g,d-g+1,d-g+2,ldots,d+g-1,d+gd−g,d−g+1,d−g+2,…,d+g−1,d+g；否则当 g≥dg geq dg≥d 时，他的机器人每次可以选择向右弹跳的距离为 1,2,3,…,d+g−1,d+g1,2,3,ldots,d+g-1,d+g1,2,3,…,d+g−1,d+g。

现在小 R 希望获得至少 kkk 分，请问他至少要花多少金币来改造他的机器人。

输入格式

第一行三个正整数 n,d,kn,d,kn,d,k ，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数之间用一个空格隔开。

接下来 nnn 行，每行两个整数 xi,six_i,s_ixi,si ，分别表示起点到第 iii 个格子的距离以及第 iii 个格子的分数。两个数之间用一个空格隔开。保证 xix_ixi 按递增顺序输入。

输出格式

共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 kkk 分，输出 −1-1−1。

样例 #1

样例输入 #1

7 4 10 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2 12345678 样例输出 #1

2 1

样例 #2

样例输入 #2

7 4 20 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2 12345678 样例输出 #2

-1 1

提示

输入输出样例 1 说明

花费 222 个金币改进后，小 R 的机器人依次选择的向右弹跳的距离分别为 $ 2, 3, 5, 3, 4,3$，先后到达的位置分别为 2,5,10,13,17,202, 5, 10, 13, 17, 202,5,10,13,17,20，对应$ 1, 2, 3, 5, 6, 7$ 这 666 个格子。这些格子中的数字之和 $ 15$ 即为小 R 获得的分数。

输入输出样例 2 说明

由于样例中 777 个格子组合的最大可能数字之和只有 181818，所以无论如何都无法获得 202020 分。

数据规模与约定

本题共 10 组测试数据，每组数据等分。

对于全部的数据满足1≤n≤5×1051 le n le 5times10^51≤n≤5×105，1≤d≤2×1031 le d le2times10^31≤d≤2×103，1≤xi,k≤1091 le x_i, k le 10^91≤xi,k≤109，∣si∣<105|s_i| < 10^5∣si∣<105。

对于第 1,21, 21,2 组测试数据，保证 n≤10nle 10n≤10。

对于第 3,4,53, 4, 53,4,5 组测试数据，保证 n≤500n le 500n≤500。

对于第 6,7,86, 7, 86,7,8 组测试数据，保证 d=1d = 1d=1。

浅浅地分析下？

n≤10n le 10n≤10 首先，如果是我去考试,这是第四题啊！这说明这什么，这题是提高组难度的！于是乎，我会去骗分我一看，那个−1-1−1的应该是最好骗的吧，直接把所有正数加起来，如果小于kkk,那就输出−1-1−1咯我的眼睛渐渐地移到了n≤10n le 10n≤10上，贪婪的目光似要把这101010分硬生生的拿chi 下diao我的念头从正数移到了……暴搜上！枚举所有可能的答案，在判断这个方案是否能达到kkk,是就输出啦那个……怎么判断这个方案怎么达到kkk?爆枚呗！每个点最多有nnn个决策，一一枚举再记忆化一下应该可以拿下这10分吧？（我没试过） n≤500n le 500n≤500

刚刚我们在分析枚举所有可能的答案时，我们是forforfor循环一个一个的枚举

有没有更优的枚举方法？

有！因为这一段格子是连续的，我们很容易想到了二分答案！

定义两个指针，lll和rrr

mid=(l+r)/2=(l+r)>>1 mid=(l+r)/2=(l+r)>>1 mid=(l+r)/2=(l+r)>>1

如果这个答案可以行(check()check()check()函数)，由于题目要求的是最小，所以答案可能在左边，r=midr=midr=mid,否则答案在右边l=mid+1l=mid+1l=mid+1

这里为什么是r=midr=midr=mid而不是r=mid−1r=mid-1r=mid−1? 因为我们输出的是rrr

现在的重点是怎么写check()check()check()函数？

我们刚刚的思路是暴力枚举，再思考一下？

线性的？每个点最多有n个决策？达到kkk?这怎么看都想动态规划啊

于是我们来设计状态，dpidp_idpi表示跳到了第iii个格子所得到的最大分数

dpi=max(dpj+a[i].value,dpi)(minn≤a[i].pos−a[j].pos≤maxx) dp_i=max(dp_j+a[i].value,dp_i)(minn le a[i].pos-a[j].pos le maxx) dpi=max(dpj+a[i].value,dpi)(minn≤a[i].pos−a[j].pos≤maxx)

这里，就有同学有疑问了(应该只有我)有没有可能往前跳？答案是不可能的

想想，如果有三个点从前到后分别是1,2,31,2,31,2,3号，往前跳指的是从111跳到333，然后跳到222,那为何不直接一次跳过去呢？所以只需要往后转移

时间复杂度为O(n2log2MAX(xi))O(n^2log_2MAX(x_i))O(n2log2MAX(xi))

这样就可以过n≤500n le 500n≤500的点了

CodeCodeCode

#include<bits/stdc++.h> using namespace std; #define INF 1e9 struct node{int pos=0,value=0; }a[500005]; int n,d,k; int dp[500005]; bool check(int minn,int maxx){dp[0]=0LL;for(int i=1;i<=n;i++){dp[i]=-INF;for(int j=0;j<i;j++)if(a[i].pos-a[j].pos>=minn&&a[i].pos-a[j].pos<=maxx)dp[i]=max(dp[i],dp[j]+a[i].value);if(dp[i]>=k) return true;}return false; } int main() {cin>>n>>d>>k;for(int i=1;i<=n;i++) cin>>a[i].pos>>a[i].value;int l=0,r=INF;while(l<r){int mid=(l+r)>>1;if(check(max(1,d-mid),d+mid)) r=mid;else l=mid+1;}cout<<(r==INF?-1:r);return 0; }

c++

运行

123456789101112131415161718192021222324252627282930313233 n≤5∗105n le 5*10^5n≤5∗105 我们考虑在50分的做法上继续优化我们看这个复杂度O(n2log2MAX(xi))O(n^2log_2MAX(x_i))O(n2log2MAX(xi))，最大的麻烦是什么？那肯定是n2n^2n2啊，有没有办法把n2n^2n2优化成nlog2nnlog_2nnlog2n或nnn呢？我们观察check()check()check()函数，发现dpdpdp的转移都是在它之前满足条件的，动态变化的，很自然的想到了单调队列所以我们只需要维护dequedequedeque就行了怎么维护呢？定义一个指针nownownow,让他指向第一个可行的点

while(a[i].pos-a[now].pos>maxx&&now<i) now++;

c++

运行

1 然后扫一遍可行的区间

while(a[i].pos-a[now].pos<=maxx&&a[i].pos-a[now].pos>=minn&&now<i){

c++

运行

1 更新一下这个点，讲不可行的点从队尾弹出，不可行包括比dpnowdp_{now}dpnow小或者超出了区间

while(!q.empty()&&(dp[q.back()]<=dp[now]||a[i].pos-a[q.back()].pos>maxx)) q.pop_back();

c++

运行

1 将新的点从队尾pushpushpush,同时，指针枚举下一个点

q.push_back(now),now++;

c++

运行

1 最后在whilewhilewhile外，将队首不可行的方案弹出

while(!q.empty()&&a[i].pos-a[q.front()].pos>maxx) q.pop_front();

c++

运行

1 最后判断和转移

if(!q.empty()) dp[i]=dp[q.front()]+a[i].value; if(dp[i]>=k) return true;

c++

运行

12 注意，nownownow千万不要重新赋值，这样才能保证每个点进出一遍时间复杂度为O(nlog2MAX(xi))O(nlog_2MAX(x_i))O(nlog2MAX(xi))记得开longlonglongquad longlonglong哦，然后你就可以ACACAC啦

CodeCodeCode

#include<bits/stdc++.h> using namespace std; #define INF 1e18 typedef long long ll; struct node{ll pos=0,value=0; }a[500005]; ll n,d,k; ll dp[500005]; bool check(ll minn,ll maxx){for(int i=1;i<=n;i++) dp[i]=-INF;dp[0]=0LL;deque<int> q;int now=0;for(ll i=1;i<=n;i++){while(a[i].pos-a[now].pos>maxx&&now<i) now++;while(a[i].pos-a[now].pos<=maxx&&a[i].pos-a[now].pos>=minn&&now<i){while(!q.empty()&&(dp[q.back()]<=dp[now]||a[i].pos-a[q.back()].pos>maxx)) q.pop_back();q.push_back(now);now++;}while(!q.empty()&&a[i].pos-a[q.front()].pos>maxx) q.pop_front();if(!q.empty()) dp[i]=dp[q.front()]+a[i].value;if(dp[i]>=k) return true;}return false; } int main() {cin>>n>>d>>k;for(ll i=1;i<=n;i++) cin>>a[i].pos>>a[i].value;ll l=1,r=a[n].pos;while(l<r){ll mid=(l+r)>>1;if(check(max((long long)1,d-mid),d+mid)) r=mid;else l=mid+1;}cout<<(r==INF?-1:r);return 0; }

c++

运行

1234567891011121314151617181920212223242526272829303132333435363738394041