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

· · 题解

P1052 [NOIP 2005 提高组] 过河

题目分析：

在长为 L 的河上分布 m 个石子，青蛙每次跳跃范围为 {s-t} 步，需从起点到终点求最少踩中石子数。

算法思路：

特殊情况：当 S=T 时直接看石子的位置是不是跳跃步数的倍数。

路径压缩：因为 L 的长度最大有 10^9 但是石头最多只有 100 个，所以我们要进行缩点操作，我们可以试着用 1∼10 这几个数把所有可以表达的数都表达出来，发现最后一个不能表达出来的书是 71，所以当石头的间隔大于 72 时就可以压缩路径，因为 1∼10 最后一个不能表示的数是 71 （可见[NOIP 2017 提高组] 小凯的疑惑）所以超过 71 的数都可以跳到。

状态转移：定义 dp_i 为到达 i 位置时最小的踩石数，所以转移方程为 \min(dp_i,dp_{i-j}+flag_i)。

关键代码：

if(a[i] - a[i-1] > 72) {
    b[i] = b[i-1] + 72;
}
else {
  b[i] = b[i-1] + (a[i] - a[i-1]);
}
  flag[b[i]] = 1;

按照上文进行缩点操作，flag_i 表示当前位置是否为石头。

AC代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=105, maxL=9e3+7; // 最大石头数和路径压缩后最大长度
ll flag[maxL];    // 标记压缩后坐标是否有石头
ll l, sum;        // 河道总长，临时计数器
ll s, m, t;       // 跳跃步数范围[s,t], 石头数，实际用t值
ll a[N], b[N];    // 原石头坐标，压缩后坐标
ll dp[maxL];      // dp[i]表示到达位置i的最小踩石数

signed main() {
    cin >> l;   
    cin >> s >> t >> m; 

    for(int i=1; i<=m; i++) {
        cin >> a[i];
    }
    // 处理特殊情况
    if(s == t) {
        for(int i=1; i<=m; i++) {
            // 统计正好在s倍数位置的石头
            if(a[i] % s == 0) sum++;
        }
        cout << sum; 
        return 0;
    }

    // 常规情况处理
    sort(a+1, a+m+1);  // 将石头位置排序
    a[m+1] = l;        // 添加终点为最后一个"虚拟石头"

    // 路径压缩：将长距离空白压缩为固定长度
    b[0] = 0; // 压缩后的起点仍为0
    for(int i=1; i<=m+1; i++) {
        // 当两石头间距大于72时，压缩为72（优化关键点）
        if(a[i] - a[i-1] > 72) {
            b[i] = b[i-1] + 72;
        } else {
            b[i] = b[i-1] + (a[i] - a[i-1]);
        }
        flag[b[i]] = 1; // 标记压缩后的石头位置（终点特殊处理）
    }
    flag[b[m+1]] = 0;  // 终点位置不需要踩

    // 初始化DP数组（初始化为极大值105，因最多100个石头）
    for(int i=1; i<=b[m+1]+t; i++) {
        dp[i] = 105;
    }

    // 动态规划核心：计算每个位置的最小踩石数
    for(int i=s; i<=b[m+1]+t; i++) {    // 遍历所有可达位置
        for(int j=s; j<=t; j++) {       // 枚举所有可能的跳跃步数
            if(i-j >= 0) {              // 确保前一位置合法
                // 状态转移：从i-j位置跳j步到i，累加当前石头标记
                dp[i] = min(dp[i], dp[i-j] + flag[i]);
            }
        }
    }

    // 寻找终点区域的最小值（可能跳过终点）
    ll ans = 105;
    for(int i=b[m+1]; i<=b[m+1]+t; i++) { // 终点及之后t个位置
        ans = min(ans, dp[i]);
    }
    cout << ans; 

    return 0;
}

谢谢收看