这是一道很复杂有趣的题目
题目描述
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下：
在地面上确定一个起点，然后在起点右侧画 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个月，真为我的懒惰而佩服）