题目背景

NOIP2017 普及组 T4

题目描述

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

跳房子的游戏规则如下：

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

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

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

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

输入格式

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

接下来 \(n\) 行，每行两个整数 \(x_i,s_i\) ，分别表示起点到第 \(i\) 个格子的距离以及第 \(i\) 个格子的分数。两个数之间用一个空格隔开。保证 \(x_i\) 按递增顺序输入。

输出格式

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

样例 #1

样例输入 #1

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出 #1

2

样例 #2

样例输入 #2

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出 #2

-1

提示

输入输出样例 1 说明

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

输入输出样例 2 说明

由于样例中 \(7\) 个格子组合的最大可能数字之和只有 \(18\)，所以无论如何都无法获得 \(20\) 分。

数据规模与约定

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

对于全部的数据满足\(1 \le n \le 5\times10^5\)，\(1 \le d \le2\times10^3\)，\(1 \le x_i, k \le 10^9\)，\(|s_i| < 10^5\)。

对于第 \(1, 2\) 组测试数据，保证 \(n\le 10\)。

对于第 \(3, 4, 5\) 组测试数据，保证 \(n \le 500\)。

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

浅浅地分析下？

\(n \le 10\)

  • 首先，如果是我去考试,这是第四题啊！这说明这什么，这题是提高组难度的！

  • 于是乎，我会去骗分

  • 我一看，那个\(-1\)的应该是最好骗的吧，直接把所有正数加起来，如果小于\(k\),那就输出\(-1\)咯

  • 我的眼睛渐渐地移到了\(n \le 10\)上，贪婪的目光似要把这\(10\)分硬生生的拿chi 下diao

  • 我的念头从正数移到了……暴搜上！

  • 枚举所有可能的答案，在判断这个方案是否能达到\(k\),是就输出啦

  • 那个……怎么判断这个方案怎么达到\(k\)?

  • 爆枚呗！每个点最多有\(n\)个决策，一一枚举再记忆化一下应该可以拿下这10分吧？（我没试过）

\(n \le 500\)

  • 刚刚我们在分析枚举所有可能的答案时，我们是\(for\)循环一个一个的枚举

  • 有没有更优的枚举方法？

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

  • 定义两个指针，\(l\)和\(r\)

  • \[mid=(l+r)/2=(l+r)>>1
    \]

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

  • 这里为什么是\(r=mid\)而不是\(r=mid-1\)? 因为我们输出的是\(r\)

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

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

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

  • 于是我们来设计状态，\(dp_i\)表示跳到了第\(i\)个格子所得到的最大分数

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

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

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

  • 时间复杂度为\(O(n^2log_2MAX(x_i))\)

  • 这样就可以过\(n \le 500\)的点了

    \(Code\)

    #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;
 }

\(n \le 5*10^5\)

  • 我们考虑在50分的做法上继续优化

  • 我们看这个复杂度\(O(n^2log_2MAX(x_i))\)，最大的麻烦是什么？

  • 那肯定是\(n^2\)啊，有没有办法把\(n^2\)优化成\(nlog_2n\)或\(n\)呢？

  • 我们观察\(check()\)函数，发现\(dp\)的转移都是在它之前满足条件的，动态变化的，很自然的想到了单调队列

  • 所以我们只需要维护\(deque\)就行了

  • 怎么维护呢？

  • 定义一个指针\(now\),让他指向第一个可行的点

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){
  • 更新一下这个点，讲不可行的点从队尾弹出，不可行包括比\(dp_{now}\)小或者超出了区间
while(!q.empty()&&(dp[q.back()]<=dp[now]||a[i].pos-a[q.back()].pos>maxx)) q.pop_back();
  • 将新的点从队尾\(push\),同时，指针枚举下一个点
q.push_back(now),now++;
  • 最后在\(while\)外，将队首不可行的方案弹出
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;

  • 注意，\(now\)千万不要重新赋值，这样才能保证每个点进出一遍

  • 时间复杂度为\(O(nlog_2MAX(x_i))\)

  • 记得开\(long\quad long\)哦，然后你就可以\(AC\)啦

\(Code\)

#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;
 }