这是一道很复杂有趣的题目
题目描述
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下：
在地面上确定一个起点，然后在起点右侧画 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 分，请问他至少要花多少金币来改造他的机器人。
若无论如何他都无法获得至少 k 分，输出 -1 。
题目链接
https://www.luogu.com.cn/problem/P3957
一、二分+深搜=20分
我们可以发现分数是根据灵活性的上升而上升的，也就是说分数对于灵活性而言是有序的。
那么我们就完全没有必要去一个个枚举分数，而是可以用二分来加快速度。
然后我们用深搜dfs非常暴力地计算最大分数，并与k比较，就可以获得TLE20分
代码如下：
#include<iostream>
#define MAXN 500005
#define INF 0x3f3f3f3f
using namespace std;
int d,n,k,minl,maxl,ans;
struct node{
int x,s;
}a[MAXN];
void dfs(int pos,int sum){
ans=max(ans,sum);
for(int i=pos+1;i<=n;i++){
if(a[i].x-a[pos].x>maxl) break;
if(a[i].x-a[pos].x<minl) continue;
dfs(i,sum+a[i].s);
}
}
bool check(int mid){
minl=max(1,d-mid);
maxl=d+mid;
ans=-INF;
dfs(0,0);
return ans>=k;
}
int main(){
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].s;
}
int l=0,r=INF;
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
if(check(l)) cout<<l;
else cout<<-1;
return 0;
}
二、二分+动态规划=50分
那么我们就需要思考加速的方法。很明显二分已经足够快了，所以导致我们TLE的罪魁祸首就是深搜。
那我们check函数里用什么呢？ 当然是动态规划啦！
我们可以发现深搜中的前后关系是线性的，所以可以用动态规划。
只要中间过程大于等于k即可，因为后面的值一定越来越大。这样做，你可以获得TLE50分。
代码如下：
#include<iostream>
#define MAXN 500005
#define INF 0x3f3f3f3f
using namespace std;
int d,n,k,minl,maxl,ans;
struct node{
int x,s;
}a[MAXN];
int f[MAXN];
bool check(int mid){
minl=max(1,d-mid);
maxl=d+mid;
for(int i=1;i<=n;i++){
f[i]=-INF;
for(int j=0;j<i;j++){
int dis=a[i].x-a[j].x;
if(dis<minl) break;
if(dis>maxl) continue;
f[i]=max(f[i],f[j]+a[i].s);
}
if(f[i]>=k) return true;
}
return false;
}
int main(){
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].s;
}
int l=0,r=INF;
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
if(check(l)) cout<<l;
else cout<<-1;
return 0;
}
三、50分+小优化=80分
我们已经用动态规划获得了50分，但还是挂了。
怎么办？俗话说：“世上无难题，只要肯放弃。”
动规挂了，我们就优化动规
在一波玄学优化后……
#include<iostream>
#define MAXN 500005
#define INF 0x3f3f3f3f
using namespace std;
int d,n,k,minl,maxl,ans;
struct node{
int x,s;
}a[MAXN];
int f[MAXN];
bool check(int mid){
minl=max(1,d-mid);
maxl=d+mid;
for(int i=1;i<=n;i++){
f[i]=-INF;
for(int j=i-1;j>=0;j--){
int dis=a[i].x-a[j].x;
if(dis<minl) continue;
if(dis>maxl) break;
f[i]=max(f[i],f[j]+a[i].s);
}
if(f[i]>=k) return true;
}
return false;
}
int main(){
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].s;
}
int l=0,r=INF;
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
if(check(l)) cout<<l;
else cout<<-1;
return 0;
}
总之就是很玄学。。。
四、二分+动态规划+单调队列优化
我们发现，在check函数中我们使用了双层循环，其实是用不着的。
第二重循环中，我们遍历了很多无效的项，这时候，我们就可以通过单调队列优化来解决。
因为如果a[i].x-a[j].x>maxl的话，a[i+1].x-a[j].x>maxl，这样j这个点后面就彻底没用了。
所以这有用吗？ 要不还是洗洗睡吧。
当然有用！
我们就可以弄个队列，对于点i，有用的时候就把它留在队列里，没用就把它踢出队列，扔进垃圾桶
这样，i这个点我们后面就不需要无效遍历了
具体代码如下
#include<iostream>
#define MAXN 500005
#define INF 0x3f3f3f3f
using namespace std;
int d,n,k,minl,maxl,ans,h,t;
struct node{
int x,s;
}a[MAXN];
int f[MAXN],q[MAXN];
void push(int i){
while(t>h&&f[q[t-1]]<f[i])
t--;
q[t]=i;
t++;
}
bool check(int mid){
minl=max(1,d-mid);
maxl=d+mid;
int j=0;
h=t=0;
for(int i=1;i<=n;i++){
f[i]=-INF;
while(j<i&&a[i].x-a[j].x>=minl) push(j++);
while(h<t&&a[i].x-a[q[h]].x>maxl) h++;
if(t==h||f[q[h]]==-INF) continue;
else f[i]=f[q[h]]+a[i].s;
if(f[i]>=k) return true;
}
return false;
}
int main(){
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].s;
}
int l=0,r=INF;
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
if(check(l)) cout<<l;
else cout<<-1;
return 0;
}
完结撒花（居然鸽了10个月，真为我的懒惰而佩服）
标签：NOIP2017,跳房子,普及,minl,int,MAXN,maxl,INF,define From： https://www.cnblogs.com/hzy-ygkl/p/16423028.html