题解 P3957 【跳房子】

Gorenstein · 2020-11-06 17:41:53 · 题解

原题链接：P3957 跳房子

题目大意

直线的正方向上有 n 个点，他们到原点的距离为 x_i，第 i 个点有一个权值 s_i。权值可能为负。
从原点开始向右跳。假设原点为第 0 个点，每次能跳到 \left[s_i+d-g,s_i+d+g\right] 中在第 i 个点右边的任意一个点，并获得对应的权值。
给定 d,k，现在想要在获得的权值之和大于等于 k 的前提下，最小化 g。

分析

容易发现，花费的金币越多，则跳跃距离的灵活度也更大。故而当金币增加时，最大得分是不降的。因此最大得分对金币数具有单调性，故二分判定 g 。

//二分判定mid（假设单调上升） 
l=0,r=100005;
while(l<r){
    long long mid=l+r>>1;
    if(check(mid))r=mid;
    else l=mid+1;
}

然后思考如何实现判定。容易发现这是一个基本的线性 DP 问题。

每一个点都需要从它左边的点跳过来，并且后面的跳法不受前面如何条约影响。同时，一个点的最大得分，是从能跳到这个点的前面所有点中选取最优的一个。

我们设 f_i 表示以 i 结尾的所有跳跃路线获得的权值中的最大值，并令 f_0=0。容易写出转移方程

f_i=\max\limits_{\{j:0\leq j<i\}}\{f_j+s_i\} \quad{}_{(d-g\leq x_i-x_j\leq d+g)}.

若发现一个 f_i 大于等于 k，直接返回 true，否则判定失败。时间复杂度 O(n^2\log n)。

//38 lines of AC_code
long long n,d,k,f[500005],a[500005][2];
bool check(int g){
    memset(f,-127,sizeof(f)); 
    long long x=max(d-g,(long long)1),s=d+g;
    f[0]=0;
    //外层循环枚举阶段i 
    for(long long i=1;i<=n;i++){
        //内层循环对决策点j进行转移 
        for(long long j=i-1;j>=0;j--){
            if(a[i][0]-a[j][0]<x)continue;
            if(a[i][0]-a[j][0]>s)break;
            //实行状态转移方程 
            f[i]=max(f[i],f[j]+a[i][1]);
            if(f[i]>=k)return true;
        }
    }
    return false;
}
int main(){
    cin>>n>>d>>k;
    for(long long i=1;i<=n;i++)
        cin>>a[i][0]>>a[i][1];
    l=0,r=100005;
    //二分判定花费mid是否可行 
    while(l<r){
        long long mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(l==100005)cout<<-1;
    else cout<<l;
    return 0;
}

单调队列优化

我们还能继续进行优化。

继续思考，容易发现，当 i 增大时，候选集合在整体的向右移。因此，此题实际上是一个移动区间求最值的问题，可用单调队列来实现。

单调队列中的元素维护的值满足单调性，并且每个元素对应在原序列中的顺序必须单调递增。每一次区间的移动，队首就是最优解。

建立单调队列 q，执行以下步骤：

对于每个阶段 i，将决策候选集合中的元素 j 从队尾插入单调队列。此题中是区间最大值，所以队首应为未过时的所有决策中最大值。内部决策单调递减；
检查队首，排除过时决策；
直接取队首作为当前状态的最优决策，实行转移；
转移过后，判断分数是否已经大于 k，如果是，返回判定成功。

所有 j 的取值最多进队和出队一次，因此单次判定的是线性的。总时间复杂度为 O(n\log n)。

//38 lines of AC_code
long long n,d,k,f[500005],a[500005][2],q[500005],l=0,r=100005;
bool check(int g){
    memset(f,-,sizeof(f));
    memset(q,0,sizeof(q));
    long long x=max(d-g,(long long)1),s=d+g;
    long long head=1,tail=0,j=0;
    f[0]=0;
    //依次转移每个i 
    for(long long i=1;i<=n;i++){  
        //决策候选集合  
        while(a[i][0]-a[j][0]>=x&&j<i){
            if(f[j]>-99999999){
                //检查队尾单调性 
                while(f[q[tail]]<=f[j]&&head<=tail)tail--;
                q[++tail]=j;//符合单调性后，插入决策j
            }
            j++;
        }
        //检查队头是否过时 
        while(a[i][0]-a[q[head]][0]>s&&head<=tail)head++;
        if(head<=tail)f[i]=f[q[head]]+a[i][1];//实行决策 
        if(f[i]>=k)return true;
    }
    return false;
}
int main(){
    cin>>n>>d>>k;
    for(long long i=1;i<=n;i++)cin>>a[i][0]>>a[i][1]; 
    //二分判定花费mid个金币是否可行 
    while(l<r){
        long long mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(l==100005)cout<<-1;
    else cout<<l;
    return 0;
}