题解：P1052 [NOIP 2005 提高组] 过河

· · 题解

P1052 [NOIP 2005 提高组] 过河 题解

Part 1：题目解法

step 1：读懂题意

青蛙尽量不要跳到石头上，但是在有些情况下无法避免不跳上去一个石头，本题需要输出这些无法避免的石头数的最小值。

step 2：思考算法

本题要用什么算法呢？显然是动态规划，我们初步的想法一定是：遍历 1 到 L 每个点，对于第 i 个点，我们把可以影响这个点的值的 dp[i-t] 至 dp[i-s] 取最小值，用 is_stone 数组表示一点是否有石头，j 从 t 到 s 循环，于是状态转移方程就是 dp[i]=dp[i-j]+is_stone[i]。

step 3：优化算法以及检查算法是否可行

但是本题的 L 在 10^9 以内，开一个长度为 10^9 的数组会炸空间，于是最直接的优化空间的方式就是缩点：

可以提前预处理一下，把该缩的点缩了，把该缩的点缩了。注意特判 s=t 的情况。

Part 2：Code


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 4000005;
ll dp[M],s,t,len,truelen,m,stone[M],dis[M],is_stone[M];
int main(){
    memset(dp,0x3f,sizeof(dp)); 
    memset(dis,0x3f,sizeof(dis));
    dp[0]=0;  //长度为0时表示起点=终点，答案为0
    cin>>len>>s>>t>>m;
    for(ll i=1;i<=m;i++) cin>>stone[i];
    sort(stone+1,stone+m+1);  //先按石头先后排序，因为题目没有保证输入时按顺序
    if(s==t){  //特判s=t的情况，如果stone[i]%s==0，说明走这一步时必须跳到第i个石头上
        ll sum=0;
        for(ll i=1;i<=m;i++){
            if(stone[i]%s==0) ++sum;
        }
        cout<<sum;
        return 0;
    }
    dis[m+1]=min(400LL,len-stone[m]); //写400LL表示把400转成 long long 类型，否则无法与 long long 类型取最小值
    for(ll i=1;i<=m;i++){
        dis[i]=min(stone[i]-stone[i-1],400LL);//如果距离太长就缩点
        truelen+=dis[i];
        is_stone[truelen]=1;
    } //truelen是缩点后的长度
    len+=dis[m+1];
    for(ll i=1;i<truelen+10;i++){
        for(ll j=s;j<=t;j++){
            if(i-j>=0) dp[i]=min(dp[i],dp[i-j]+is_stone[i]);  //i-j>=0 判断 i>=j 的情况，避免减成负数RE
        }
    }
    ll ans=M*10; //赋较大初始值
    for(ll i=truelen;i<truelen+10;i++){ //因为青蛙最多跳到终点位置+10，减去终点自己，就是从truelen到truelen+9可能为答案，把这些候选取最小值就是最终答案
        ans=min(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}

完结撒花！