过河

题目大意
一条长度为L的河，某些地方有石头，每次可以跳S~T的长度。求最少踩到几块石头。

算法
DP，f[i]=f[i-j]+flag[i]。但是河的长度有1e9，所以我们要压缩路径。

若两个石子之间的距离大于t(t-1)，我们就可以把它改成t(t-1)。

然后DP就好了

代码

#include <cstdio>
#include <algorithm>
#define INF 1<<30
int a[101],dis[101],flag[10001],f[10001];
int main(){
    int l,s,t,n;
    scanf("%d%d%d%d",&l,&s,&t,&n);
    if(s==t){
        int cnt=0;
        for(int i=1;i<=n;i++){
            int tt;
            scanf("%d",&tt);
            cnt+=(tt%s==0);
        }
        printf("%d\n",cnt);
        return 0;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    std::sort(a+1,a+n+1);
    dis[n+1]=std::min(l-a[n],100);
    l=0;
    for(int i=1;i<=n;i++){
        dis[i]=std::min(a[i]-a[i-1],90);
        l+=dis[i];
        flag[l]=1;
    }
    l+=dis[n+1];
    for(int i=1;i<=l+9;i++){
        f[i]=INF;
        for(int j=s;j<=t;j++)
            if(j<=i)
                f[i]=std::min(f[i],f[i-j]+flag[i]);
    }
    int mn=INF;
    for(int i=l;i<=l+9;i++)
        mn=std::min(f[i],mn);
    printf("%d\n",mn);
    return 0;
}