自动搬运

查看原文

来自洛谷，原作者为

	Tweetuzki AFO

搬运于2025-08-24 21:54:34，当前版本为作者最后更新于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，就是单调队列的模板题。单调队列要想优化 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 ）

代码：

#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;
}