题解：P3957 [NOIP2017 普及组] 跳房子

· · 题解

题目传送门。

老师、学长在讲 DP 的优化，同时我觉得题解区一些题解讲的不太清楚，因此来说一下个人的理解。

如有不足，欢迎指出。

什么是动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。划分出的每个子问题，通过一个公式，也就是状态转移方程联系起来，最后得到全局最优解。

题目分析

基本思路

根据题目的描述，发现很难用贪心与搜索实现，考虑用动态规划来实现，标签都说了。

一开始做的时候，对于金币的使用，我很是困惑，但是仔细想金币的作用，无非是扩大了跳跃的范围使机器人能够达到的范围更广，而求最小金币无非是枚举范围内的金币，看何时用最小金币满足条件（不一定要得到最高分数）。

暴力

虽然可以直接讲正解，但是还是讲讲暴力的做法来方便理解一下学长也是先让我们打暴力。

既然已经知道这是一道动态规划题目，写动态规划类的题目关键是设出状态，求出状态转移方程。

设 f_i 为跳到第 i 个点的最大分数。

状态设完，就是求出状态转移方程了，金币如何并不会直接影响到 f_i 的值，影响到当前 f_i 的值的因素仅仅是跳到上一个格子的值与当前第 i 个格子 s_i 的值，也就能得到状态转移方程 f_i= \max {f_j}+s_i（f_i 为当前格子，f_j 为上一个格子），而金币则是用来延长条约距离，获得能到达的更远的格子，那么求出最小的金币数直接枚举范围内的金币数即可，顺序枚举，看当前数量的金币是否能满足条件。当然金币能延长的距离是有限的，由于有枚举顺序，那么如果第 j 格子与格子 i 的距离大于最远能跳到的距离，那么之后的那些格子也跳不了，也就是求完了当前金币数量下所能跳到的格子，因此可以直接 break;。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll n,d,k,l=0,r=N,mid;
//假设当前格子为i
ll f[N],x[N],s[N];//跳到第i个点的最大分数 第i个格子的距离 第i个格子的分数

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
bool find(int g){//查看金币是否能满足条件 
    memset(f,-N,sizeof(f));//初始化 由于可以为负数 
    f[0]=0;//一开始在0点 
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>=0;j--){
            if(x[i]-x[j]>d+g){//如果超出范围
                break;//停止循环 
            }//优化

            if(x[i]-x[j]<max(ll(1),(d-g))){//注意类型 不能直接写 1 
                continue; 
            }
            f[i]=max(f[i],f[j]+s[i]);//状态转移方程 
            if(f[i]>=k){//满足条件 
                return true;
            }   
        }
    }
    return false;
}
int main(){
    ll maxn=0;
    n=read(),d=read(),k=read();//快读输入
    for(int i=1;i<=n;i++){
        x[i]=read(),s[i]=read();
        maxn=max(maxn,x[i]);
    }
    ll g=2;//金币数从0开始枚举 
    while(g+d<maxn){//范围内 
        if(find(g)){
            cout<<g<<'\n'; 
            return 0;
        }
        g++;
    }
    cout<<-1<<endl;
    return 0; 
}

暴力代码大概只能过一半测试点，剩下的都超时了。

优化

作为 T4 肯定不会那么容易让你做出来的。刚刚的代码大概是 O(n^2) 的时间复杂度，看数据范围 n \le 10^5，因此如果暴力做法会超时。

那么就是考虑优化了，看动态规划部分似乎没有什么可以改的了，那枚举金币的呢？

可以发现，由于金币数量是有序的，那么即可用二分查找来解决，对范围内的金币数进行二分查找，假如已经满足，将缩小金币数范围，减小金币数量，继续查找。假如还不能满足，则缩小金币数范围，增大金币数量使能到达的格子更多。

附上 AC 代码 ↓。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll n,d,k,l=0,r=N,mid;
//假设当前格子为i
ll f[N],x[N],s[N];//跳到第i个点的最大分数 第i个格子的距离 第i个格子的分数

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
bool find(int g){//查看金币是否能满足条件 
    memset(f,-N,sizeof(f));//初始化 由于可以为负数 
    f[0]=0;//一开始在0点 
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>=0;j--){
            if(x[i]-x[j]>d+g){//如果超出范围
                break;//停止循环
            }//优化

            if(x[i]-x[j]<max(ll(1),(d-g))){//注意类型 不能直接写1 如果距离为负按1来算
                continue;
            }
            f[i]=max(f[i],f[j]+s[i]);//状态转移方程
            if(f[i]>=k){//满足条件
                return true;
            }   
        }
    }
    return false;
}
int main(){
    n=read(),d=read(),k=read();//快读输入
    for(int i=1;i<=n;i++){
        x[i]=read(),s[i]=read();
    }

    while(l<r){//由于是单调的序列可以使用二分
        mid=(l+r)>>1;//直接平均可能会溢出
        if(find(mid)){//看是否每个硬币都能做到
            r=mid;
        }
        else{//不能满足
            l=mid+1;//用更多金币尝试
        }
    }
    if(l==N){//无法满足分数
        cout<<-1;
    }
    else{//满足输出长度
        cout<<l;
    }   
    return 0;
}