题目：过河
思路：
因为L的值太大，而实际有石子的地方却并不多，所以要先进行离散化。
即将每个石子之间的差距都控制在刚好比t大一点的位置，这样就不会影响最终结果。
令f[i]表示跳过前i个位置需要最少踩得石头数量，转移方程f[i]=min(f[i+j]+cnt[i],f[i])，j∈[s，t]。
注意最后的输出是min{f[i]}，i∈[L，L+t）。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxd 10
#define maxm 100
#define maxl 200000
#define inf (1<<30)int L;
int s,t,m;
int a[maxm+5]= {0};
int cnt[maxl+5]= {0};
int f[maxl+5]= {0};void readin() {scanf("%d",&L);scanf("%d%d%d",&s,&t,&m);for(int i=1; i<=m; i++) {scanf("%d",&a[i]);}a[m+1]=L;sort(a+1,a+m+2);L=0;for(int i=1; i<=m+1; i++) {if(a[i]-a[i-1]>t) L+=(a[i]-a[i-1])%t+t;else L+=a[i]-a[i-1];cnt[L]++;}cnt[L]=0;
}int dp() {for(int i=1; i<L+t; i++) {f[i]=inf;for(int j=s; j<=t; j++) {int k=i-j;if(k>=0) {f[i]=min(f[k]+cnt[i],f[i]);}}}int ans=inf;for(int i=L; i<L+t; i++) {ans=min(f[i],ans);}return ans;
}int main() {readin();int ans=dp();printf("%d",ans);return 0;
}