2017年T4 跳房子（100分）

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

跳房子的游戏规则如下：

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

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

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

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

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

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

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

思路：去二分金币数量，用Dp进行计算，不然爆搜肯定肯定过不了。我之前有一次在里面求值，然后求出来再在外面与k比较，然而90分，很奇怪，有哪位奆佬能解释一下吗？谢谢！

#include<bits/stdc++.h>
using namespace std;
int n,a[500001],b[500001],d,k,ans=-1,f[500001];
int dp(int x,int y){
	int maxn=-1e10;
	memset(f,-127,sizeof(f));
	f[0]=0;
	if(x<=0){
		x=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>=0;j--){
			if(a[i]-a[j]<x){
				continue;
			}
			if(a[i]-a[j]>y){
				break;
			}
			f[i]=max(f[i],f[j]+b[i]);
			if(f[i]>maxn){
				maxn=f[i];
			}
		}
	}
    //cout<<maxn<<endl;
	return maxn;
}
int main(){
	scanf("%d%d%d",&n,&d,&k);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
	}
	int l=1,r=10005;
	while(l<=r){
		int mid=(l+r)/2;
		int d1=d-mid,d2=d+mid;
		int s=dp(d1,d2);
		if(s>=k){
			r=mid-1;
			ans=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<ans;
}

然后这一次，我就直接在函数里面直接比较，然后就过了，我也不知道为什么，下面是满分代码。

#include<bits/stdc++.h>
using namespace std;
long long n,a[500001],b[500001],d,k,ans=-1,f[500001];
bool dp(int x,int y) {
	memset(f,-127,sizeof(f));
	f[0]=0;
	if(x<=0) {
		x=1;
	}
	for(int i=1; i<=n; i++) {
		for(int j=i-1; j>=0; j--) {
			if(a[i]-a[j]<x) {
				continue;
			}
			if(a[i]-a[j]>y) {
				break;
			}
			f[i]=max(f[i],f[j]+b[i]);

		}
	}
	for(int i=1; i<=n; i++) {
		if(f[i]>=k) {
			return true;
		}
	}
	//cout<<maxn<<endl;
	return false;
}
int main() {
	scanf("%lld%lld%lld",&n,&d,&k);
	for(int i=1; i<=n; i++) {
		scanf("%lld%lld",&a[i],&b[i]);
	}
	long long l=1,r=10005;
	while(l<=r) {
		long long mid=(l+r)/2;
		long long d1=d-mid,d2=d+mid;
		bool s=dp(d1,d2);
		if(s==true) {
			r=mid-1;
			ans=mid;
		} else {
			l=mid+1;
		}
	}
	cout<<ans;
}