【NOIP 2017PJ】跳房子

　

跳房子

题目描述

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

跳房子的游戏规则如下：

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

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

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

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

$1\le n\le 500000$1≤n≤500000，$1\le d\le 2000$1≤d≤2000，$1\le x_i$1≤xi​，$s\le 10^9$s≤109，$\mathrm{\mid }{s}_i\mathrm{\mid }\&lt;10^5$∣si​∣<105。

算法分析

心情简单……

不难想到二分后动态规划，发现 DP 转移方程实际上在求一个动态的区间最值，就可以用单调队列优化。

第一次写就要想明白：满足条件的状态其 $x$x 值在 $\left[x\right[i]-d-g,x[i]-d+g]$[x[i]−d−g,x[i]−d+g] 范围内，单独定义一个变量储存当前插入到哪个了。

调试起来很复杂啊，记得开 $64$64 位整数。

代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long int ll;
const int maxn=500005;
char buf[1<<15],*fs=buf,*ft=buf;
inline char gc() {
	if(fs==ft) {
		ft=(fs=buf)+fread(buf,1,1<<15,stdin);
		if(fs==ft) return 0;
	}
	return *fs++;
}
template <typename T>
inline void read(T &num) {
	char c=gc();int f=num=0;
	while(c<'0'||'9'<c) {if(c=='-') f=1;c=gc();}
	while('0'<=c&&c<='9') {num=num*10+c-'0';c=gc();}
	if(f) num=-num;
}
int n,d,k,x[maxn],s[maxn],Q[maxn],head,tail,nxt;ll f[maxn];
inline bool check(int g) {
	memset(f,0xc0,sizeof(f));f[0]=0;head=0;tail=-1;nxt=0;
	for(register int i=1;i<=n;++i) {
		while(nxt<i&&x[nxt]<=x[i]-d+g) {
			while(head<=tail&&f[Q[tail]]<=f[nxt]) --tail;
			Q[++tail]=nxt++;
		}
		while(head<=tail&&x[Q[head]]<x[i]-d-g) ++head;
		if(head<=tail) f[i]=f[Q[head]]+s[i];
	}
	ll ans=0;
	for(register int i=1;i<=n;++i) ans=std::max(ans,f[i]);
	return ans>=k;
}
int main() {
	freopen("jumpplane.in","r",stdin);freopen("jumpplane.out","w",stdout);
	read(n);read(d);read(k);
	for(register int i=1;i<=n;++i) {read(x[i]);read(s[i]);}
	int l=0,r=500000,mid;
	while(l<r) check(mid=((l+r)>>1))?r=mid:l=mid+1;
	printf("%d\n",l);
	fclose(stdin);fclose(stdout);
	return 0;
}

相关阅读

NOIP 2003 传染病控制

题目背景 近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传

【NOIP2017】跳房子

这题我0分。比赛时，我一眼出正解，哈哈，太水了！这题不就是一个二分+DP+单调队列吗？然而，细节决定成败。我错了许多细节，就挂了。我只考了0