题解 P3957 【跳房子】

Tweetuzki

2017-11-25 14:04:07

Solution

这题是第四题,对于我这种蒟蒻来讲是不可能 AC 的,所以先想着骗分。什么时候不能得到目标分数呢?如果所有正数分数都加起来还小于目标分数,那就得不到目标分数。所以先特判 $-1$。 再看看这一题,我想起了 NOIP2015 提高组的“跳石头”,那题不是二分吗?这题也好像啊……于是果断使用二分求解。确定下来二分了,那么就来考虑,怎样判断二分的这个答案可不可以,显然使用动态规划。 $dp[i]$ 表示跳到第 $i$ 个格子时所能得到的分数最大值,若跳不到该格,则 $dp[i]=-\infty$。为了动规方便,再加入起点的格子,显然,起点格子离原点的距离为 $0$,格子上的值也为 $0$。状态转移方程:设 $max(l,r)$ 表示 $[l,r]$ 区间内能跳到的格子中的最大值,则 $dp[i]=\max($点 $i$ 到原点的距离 $-mid$,点 $i$ 到原点的距离 $+mid)$。 用没有优化的 DP,时间复杂度是二维的,对于 $50\%$ 的数据可以过,但是对于另外 $50\%$ 的数据 $n=500000$,即使两秒的时限也是超得不爱超了。怎么优化 DP 呢? 有一个叫单调队列的东西,专门取区间内的最大最小值。在 POJ 上,有一题叫做[Sliding Window](http://poj.org/problem?id=2823),就是单调队列的模板题。单调队列要想优化 DP,必须得保证 $l$ 和 $r$ 是单调递增或递减的。而在本题中,在向右 DP 时,上述的状态转移方程在 $dp[i]=\max($点 $i$ 到原点的距离 $-mid$,点 $i$ 到原点的距离 $+mid)$ 的 $mid$ 不变的情况下,随着 $i$ 离原点越来越远,$l$ 和 $r$ 越来越大,所以也是单调递增的。这样一优化,DP 的时间复杂度就降至一维,对于最大的 $n=500000$,就能在 2 秒的时限内轻松通过了。 upt: 感谢各位指正,现以修复代码中原有的 bug。我原来犯的错误有: 1. dp 数组初始值不能设为 $-1$,应该设为 $-\infty$,在代码中体现为 $\text{0x8080808080808080}$。 2. 二分的右边界应该取 $d$ 与第 $n$ 个格子到原点的距离的较大值,因为 $d$ 与第一个格子间距离可能大于第 $n$ 个格子到原点的距离。(感谢 @Bartholomew 的 Hack 数据 `1 42 14 20 23 `) 代码: ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=500000; const long long neInf=0x8080808080808080; struct gezi { int juli; int zhi; } a[maxn+1]; long long dp[maxn+1]; int q[maxn+1]; int n,d,k,lbound,rbound,ans=-1; long long sum; void kuaidu(int &p) { char c; int f=1; p=0; do { c=getchar(); if (c=='-') f=-1; } while (c<'0'||c>'9'); do p=p*10+c-'0', c=getchar(); while (c>='0'&&c<='9'); p=p*f; } void init() { cin>>n>>d>>k; for (int i=1; i<=n; i++) { kuaidu(a[i].juli); kuaidu(a[i].zhi); if (a[i].zhi>0) sum+=a[i].zhi; } rbound=max(a[n].juli,d); } long long dynamic_programming(int zuo, int you) { memset(dp,0x80,sizeof(dp)); dp[0]=0; memset(q,0,sizeof(q)); int tou=1, wei=0, j=0; /*for (int i=1; i<=n; i++) for (int j=0; j<i; j++) if (a[i].juli-a[j].juli>=zuo&&a[i].juli-a[j].juli<=you&&dp[j]!=neInf) dp[i]=max(dp[i],dp[j]+a[i].zhi);*/ for (int i=1; i<=n; i++) { while (a[i].juli-a[j].juli>=zuo&&j<i) { if (dp[j]!=neInf) { while (tou<=wei&&dp[q[wei]]<=dp[j]) wei--; q[++wei]=j; } j++; } while (tou<=wei&&a[i].juli-a[q[tou]].juli>you) tou++; if (tou<=wei) dp[i]=dp[q[tou]]+a[i].zhi; } long long num=neInf; for (int i=1; i<=n; i++) if (dp[i]>num) num=dp[i]; return num; } int main() { //freopen("jump.in","r",stdin); //freopen("jump.out","w",stdout); init(); if (sum<k) { cout<<"-1"<<endl; return 0; } while (lbound<=rbound) { int mid=(lbound+rbound)/2; int zuobianjie=max(1,d-mid); int youbianjie=d+mid; long long num=dynamic_programming(zuobianjie,youbianjie); if (num<k) lbound=mid+1; else { ans=mid; rbound=mid-1; } } cout<<ans<<endl; //fclose (stdin); //fclose (stdout); return 0; } ```