题解 P1052 【过河】

· · 题解

NOIP2005 提高组——过河

​ by - Actinoi 2019/5/30

为获取最佳阅读效果，建议访问Actinoi's blog:过河

​  观察数据，我们发现，独木桥的长度 L\leq10^9 ，而石子的数量最多只有 100 个。因此，我们便可以考虑用离散化来解决这道题目。

​  我们用 stone 数组来存储每个石子的坐标，读入之后进行离散化操作。

离散化具体实现过程

​  我们并不知道输入是不是按从小到大有序输入的，因此我们先从小到大排序。

 排完序之后，我们从第一个石子开始进行离散化。

​ 若第 i 石子与第 i - 1 个石子之间的距离大于 s \times t ，我们便可以将这颗石子与上一颗石子的距离简化为 (stone[i] - stone[i - 1]) \% t + t * s ，这样可以将桥长 L 压缩到 10000 以内。然后用 bridge 数组来存储离散化之后桥上石子的分布情况。

如图，我们设stone[1] = 3, stone[2] = 10, s = 1, t = 2的话，便会得到上图。然后我们压缩 stone[2] 与 stone[1] 之间的距离，便会得到下图的 birdge[2] 。

那么，这为什么是正确的呢？我们不难发现，stone[2] 减去 n 个 t 之后就可以得到 bridge[2] ，所以说，凡是能够到达 stone[2] 的点也一定可以到达 bridge[2] ，所以这个思路是正确的。

​ 之后，我们用 identifier 数组存储离散化之后的桥长，用 sum 数组存储跳到桥上每一点最少需要踩到的石子数。我们从跳跃的最小距离 s 枚举到最大距离 t ，用变量 j 存储所枚举的距离，我们很容易得到状态转移方程 sum[i] = min(sum[i], sum[i - j] + bridge[i]) 。但是，从离散化之后桥上第 1 个点开始计算最小经过的石子数，但是要计算到哪呢？观察下图，我们可以发现，在identifier ～ identifier + t 之内都可以跳到终点，因此计算范围为 1 ～ identifier + t 。

​  剩下的就很简单啦，通过上面的分析，答案就在 identifier ~ identifier + t 之内，因此我们枚举这个区间内的 sum 值，找出最小值，这便是我们的答案辣!

最后附上代码:

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int stone[101], sum[10001];
bool bridge[100001]; //存储离散化之后桥上石子的分布情况
int main(){
    int l, s, t, m; //桥长，青蛙一次跳跃的最小距离，最大距离及桥上石子的个数
    cin >> l >> s >> t >> m;
    memset(sum, 0x3f, sizeof(sum)); //初始化sum数组
    for(int i = 1; i <= m; i++)
        cin >> stone[i];
    sort(stone, stone + m + 2);
    int identifier = 0;
    for (int i = 1; i <= m + 1; i++) {
        if (stone[i] - stone[i - 1] <= t * s)
            identifier += stone[i] - stone[i - 1];
        else
            identifier += (stone[i] - stone[i - 1]) % t + t;
        bridge[identifier] = true;
    }
    sum[0] = 0;
    for (int i = 1; i <= identifier + t; i++)
        for (int j = s; j <= t; j++)
            if ((i - j) >= 0)
                sum[i] = min(sum[i], sum[i - j] + bridge[i]);
    int ans = 0x3f;
    for (int i = identifier; i <= identifier + t; i++)
        ans = min(ans, sum[i]);
    cout << ans;
    return 0;
}

若您有任何建议与纠正，欢迎提出！谢谢！