过河

题目

在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

输入输出格式

输入格式:

输入文件river.in的第一行有一个正整数L(1 <= L <= 10^9),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。

输出格式:

输出文件river.out只包括一个整数,表示青蛙过河最少需要踩到的石子数。

输入输出样例

输入样例

10

2 3 5

2 3 5 6 7

输出样例

2

思路

设一次可走p步或(p-1)步

现在我们从(p-1)×p位置开始逐一推算可行性

(p-1)p+1=(p-2)p+(p+1)

(p-1)p+2=(p-3)p+2(p+1)

(p-1)p+3=(p-4)p+3(p+1)

……

(p-1)p+(p-1)=(p-p)p+(p-1)(p+1)

又上可知对于间隙大于等于p(p-1)的可以直接变为p(p-1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define F(i, x, y) for(int i=x; i<=y; i++)
#define R(i, x, y) for(int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for (flag = false, ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) flag |= ch == '-';
for (x = 0; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
x = flag ? -x : x;
}
int l, s, t, m, dis[105], now[105], now_len, f[10000000];
inline int work()
{
in(l);in(s);in(t);in(m);
F(i, 1, m) in(dis[i]);
dis[++m] = l;
if (s == t)
{
int ans = 0;
F(i, 1, m) if (dis[i] % s == 0) ans ++;
printf("%d\n", ans);
return 0;
}
sort(dis + 1, dis + m + 1);
int w = t * (t - 1);
F(i, 1, m)
{
if(dis[i] - dis[i-1] > w) now[i] = now[i-1] + w;
else now[i] = now[i-1] + (dis[i] - dis[i-1]);
now_len = max(now_len, now[i]);
}
memset(f, 127/3,sizeof(f));
f[0] = 0;
int ret1 = 1;
F(i, 1, now_len)
{
F(j, s, t)
{
if(i == now[ret1] && i != now[m])
{
if (i - j >= 0)
f[i] = Min(f[i], f[i-j]+1);
}
else
{
if (i - j >= 0)
f[i] = Min(f[i], f[i-j]);
}
}
if (i == now[ret1]) ret1 ++;
}
printf("%d\n", f[now_len]);
}
int TAT = work();
int main() {;}