题解 P3957 【跳房子】
Tweetuzki
2017-11-25 14:04:07
这题是第四题,对于我这种蒟蒻来讲是不可能 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;
}
```