题目摘自RQNOJ：http://www.rqnoj.cn/Problem_17.html
题目描述
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
对于30%的数据，L <= 10000；
对于全部的数据，L <= 10^9。
输入格式
输入的第一行有一个正整数L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
输出格式
输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。
样例输入
10
2 3 5
2 3 5 6 7
样例输出
2
题解：
应WK大神的要求，还是把这道题的题解给写了。
首先第一思路肯定是个背包，用f[i]表示走到i这个格子最少需踩多少石子，状态转移方程为1、i有石子:f[i]=min(f[i-step]+1)(s<=step<=t) 2、i无石子:f[i]=min(f[i-step])(s<=step<=t)。但是L<=10^9，就赤裸裸地TLE了，所以必须优化。
观察到一个很有用的条件，1<=S<=T<=10，也就是说每次最多跳10的距离，另外M<=100，石子数非常少，也就是说有很长的没有任何意义的区间，那么减少转移次数就从这里入手。
考虑1<=S<=T<=10，当S=T时，这个只有一种跳法，特殊处理。当S!=T时，我们考虑从起点出发，有哪些长度是走不到的，那些长度是能走到的，可以证明，大于等于T*（T-1）的长度时，一定是可以走到的（不要问我为什么，这是常识），由于T<=10，我们可以考虑为只要距离大于100的一定可以从起点到达，距离100以内的则可以用一个简单DP提前预处理出来。同理，一旦两个点的距离大于了100，那么它们一定可以由其中的一个到达另一个。也就是说，任意两个距离大于一百的点都可以把他们的距离缩小为100，而这不会对答案有任何的影响。于是我们只需要把所有石子的坐标排个序，距离大于100的缩为100，这样最多的长度也只有100*100左右，然后，裸的DP即可。
最后还是 sro sro sro sro sro WK大神牛 orz orz orz orz orz
这题是很早以前写的了，代码非常丑，也不想重写，就这样吧。
View Code
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4
5 using namespace std;
6
7 const int maxn=200000;
8
9 int l,s,t,m,a,b,dp[maxn],sb[101],ans,now;
10
11 bool stone[maxn];
12
13 int qsort(int a,int b)
14 {
15 int c,d,e,f;
16 c=a;
17 d=b;
18 e=sb[(a+b)>>1];
19 do
20 {
21 while (sb[c]<e)
22 c++;
23 while (e<sb[d])
24 d--;
25 if (c<=d)
26 {
27 f=sb[c];
28 sb[c]=sb[d];
29 sb[d]=f;
30 c++;
31 d--;
32 }
33 }while (c<=d);
34 if (c<b) qsort(c,b);
35 if (a<d) qsort(a,d);
36 return(0);
37 }
38
39 int main()
40 {
41 freopen("river.in","r",stdin);
42 freopen("river.out","w",stdout);
43
44 scanf("%d",&l);
45 scanf("%d%d%d",&s,&t,&m);
46 if (s==t)
47 {
48 for (a=1;a<=m;a++)
49 {
50 scanf("%d",&b);
51 if (b % s==0) ans++;
52 }
53 printf("%d\n",ans);
54 return(0);
55 }
56 for (a=1;a<=m;a++)
57 scanf("%d",&sb[a]);
58 qsort(1,m);
59 memset(stone,false,sizeof(stone));
60 sb[0]=0;
61 for (a=1;a<=m;a++)
62 {
63 if (sb[a]-sb[a-1]>=s*t*2)
64 {
65 now=sb[a]-sb[a-1]-2*s*t;
66 for (b=a;b<=m;b++)
67 sb[b]=sb[b]-now;
68 }
69 stone[sb[a]]=true;
70 }
71 memset(dp,0x3f,sizeof(dp));
72 dp[0]=0;
73 l=sb[m]+t+1;
74 for (b=s;b<=l;b++)
75 for (a=s;a<=t;a++)
76 if (b-a>=0)
77 {
78 if (stone[b]==true) now=1+dp[b-a];
79 else now=dp[b-a];
80 if (now<dp[b])
81 {
82 dp[b]=now;
83 }
84 }
85 printf("%d\n",dp[l]);
86
87 return 0;
88 }