NOIP2005提高组——过河
题目描述
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：（其中是桥的长度）。坐标为的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是到之间的任意正整数（包括）。当青蛙跳到或跳过坐标为的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度，青蛙跳跃的距离范围，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
输入输出格式
输入格式：
第一行有个正整数，表示独木桥的长度。
第二行有个正整数，分别表示青蛙一次跳跃的最小距离，最大距离及桥上石子的个数，其中,。
第三行有个不同的正整数分别表示这个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
输出格式：
一个整数，表示青蛙过河最少需要踩到的石子数。
输入输出样例
输入样例#1：
10
2 3 5
2 3 5 6 7
输出样例#1：
2
说明
对于30%的数据，；
对于全部的数据，。
2005提高组第二题
题解：
观察数据，我们发现，独木桥的长度 ，而石子的数量最多只有 个。因此，我们便可以考虑用离散化来解决这道题目。
我们用 数组来存储每个石子的坐标，读入之后进行离散化操作。
离散化具体实现过程
我们并不知道输入是不是按从小到大有序输入的，因此我们先从小到大排序，排完序之后，我们从第一个石子开始进行离散化。
若第 石子与第 个石子之间的距离大于 ，我们便可以将这颗石子与上一颗石子的距离简化为 ，这样可以将桥长 压缩到 以内。然后用 数组来存储离散化之后桥上石子的分布情况。
如图，我们设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] ，所以这个思路是正确的。
之后，我们用 数组存储离散化之后的桥长，用 数组存储跳到桥上每一点最少需要踩到的石子数。我们从跳跃的最小距离 枚举到最大距离 ，用变量 存储所枚举的距离，我们很容易得到状态转移方程 。但是，从离散化之后桥上第 个点开始计算最小经过的石子数，但是要计算到哪呢？观察下图，我们可以发现，在 ～ 之内都可以跳到终点，因此计算范围为 。
剩下的就很简单啦，通过上面的分析，答案就在 ~ 之内，因此我们枚举这个区间内的 值，找出最小值，这便是我们的答案辣!
最后附上代码:
#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;
}