P3957 [NOIP 2017 普及组] 跳房子

题目描述

给出 \(n\) 个点的坐标 \(a_i\) 和权值 \(s_i\)，每次向右移动正距离 \(p\)，满足 \(d-x \le p \le d+x\) 且落在给定的点上，求使经过点值的最大和不小于 \(k\) 的最小 \(x\)。

思路

step1-二分答案

这道题我们要求的是最小的 \(x\)，可显然我们无法将 \(x\) 设计到状态中去，然而，给定 \(x\) 求点值和的最大值，这一类问题是可以实现的。

所以，我们就可以以二分答案的方式列举出 \(x\) 的值，然后带入固定的 \(x\) 值求出最大的点值和 \(sum\)，判断若 \(sum \ge k\) 则查找左区间，否则查找右区间，可以在 \(O(\log n)\) 的时间复杂度内解决，十分可以接受。

还有要注意每次我们进行二分时都要将用过的元素初始化一遍。

step2-动态规划

给定了 \(x\)，怎么样求最大的点值和呢？我们可以使用动态规划解决问题，令 \(f_i\) 表示走到第 \(i\) 个点最大的点值和，其值就等于最大满足条件的 \(f_j\) 加上自己的权值，据此我们不难列出线性状态转移方程。

\[f_i= \max_{0 \le j \le i-1,d-x \le a_i-a_j \le d+x} f_j+s_i \]

实现也很容易，二重循环即可，因为有负数所以我们答案要取所有 \(f_i\) 的最大值，下列即实现代码。

bool check(int x)
{ll ans=-1e14;for(int i=1;i<=n;i++){for(int j=0;j<=i-1;j++){if(a[i]-a[j]<=d+x&&a[i]-a[j]>=d-x)//满足距离限制{f[i]=max(f[i],f[j]+s[i]);//转移}}ans=max(ans,f[i]);}return ans>=k; 
}

时间复杂度 \(O(n^2)\)，加上二分查找总复杂度 \(O(n^2\log n)\)，十分不能接受，期望得分50pts，考虑优化。

step3-单调队列优化

根据题目，我们可以知道 \(a_i\) 单调递增，所以对于决策点的选择就必然满足决策单调性，也就是说点 \(i\) 所的转移点一定是和 \(i-1\) 相同或在其之后的。那么，我们思考当一个点已经不满足 \(i\) 点的距离限制，那么对于 \(i\) 之后的点，也必然不满足后面所有点的限制条件，我们就可以用单调队列来实现这一题目了，还要注意因为 \(d-x \le p\) 的限制，我们不能直接插入点 \(i\) 到优先队列中，要枚举到位于 \(i\) 后面的点 \(k\) 时满足 \(d-x \le a_k-a_i\) 时再将 \(i\) 加入队列中。

这样一来，总时间复杂度就优化到了 \(O(n\log n)\)，十分可以接受，此题完成。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=5e5+10;
int n,d;
ll k;
int a[M],s[M];
ll f[M];
int l=0,r=1e9,mid;
bool check(int x)
{deque<int> q;ll ans=-1e14;int j=0;for(int i=1;i<=n;i++){while(a[i]-a[j]>=d-x&&j<=i-1){while(!q.empty()&&f[j]>=f[q.back()]) q.pop_back();q.push_back(j);j++;}while(!q.empty()&&a[i]-a[q.front()]>d+x) q.pop_front();if(!q.empty()) f[i]=f[q.front()]+s[i];ans=max(ans,f[i]);}return ans>=k; 
}
int main()
{int flag=0;scanf("%d%d%lld",&n,&d,&k);for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&s[i]);}while(l<=r){for(int i=1;i<=n+1;i++) f[i]=-1e14;f[0]=0;mid=(l+r)>>1;if(check(mid)) flag=1,r=mid-1;else l=mid+1;}if(!flag) printf("-1\n");else printf("%d\n",l);return 0;
}