洛谷3957 [NOIP2017PJ]跳房子

题意

有 $N$ 个格子，每个格子有权值。最开始每次只能跳 $d$ 格，可以通过改进跳 $d-g..d+g$ 格。求满足能获得最少 $k$ 权值的最小的 $g$ 。

$N\le 500000$ 。

题解

可以对 $g$ 二分答案，然后进行验证。

令 $f[i]$ 为前 $i$ 个格子可以获得的最大权值，转移方程式为：

$$f[i] = \max_{j=1}^{i-1} f[j]+s[i] \ (d-g\le x[i]-x[j]\le d+g)$$

这样显然会超时。不过可以发现决策具有单调性，所以用 $last$ 记录上一次决策，$j$ 的范围就变成 $last\le j \le i-1$ 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,d,k,x[500005],s[500005];
long long f[500005];

inline bool check(int mid)
{
    int l=max(1,d-mid),r=d+mid;
    memset(f,-0x3f,sizeof(f));
    f[0]=0;
    for (int i=1,last=0,cur=0;i<=n;i++)
    {
        for (int j=i-1;j>=last;j--)
        {
            if (x[i]-x[j]>r) break;
            if (x[i]-x[j]<l) continue;
            if (f[j]+s[i]>f[i])
            {
                cur=j;
                f[i]=f[j]+s[i];
            }
        }
        last=cur;
        if (f[i]>=k) return 1;
    }
    return 0;
}

signed main()
{
    n=read(); d=read(); k=read();
    for (int i=1;i<=n;i++) x[i]=read(),s[i]=read();
    int l=0,r=1e9;
    while (l<r)
    {
        int mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    if (r==1e9) return 0&puts("-1");
    return !printf("%d",l);
}