思路

首先，这道题还是比较容易能想到可能可以用dp解决的，因为最终的结果可以由前面的问题的解推出，具有最优子结构的特点。
然而，问题是桥长度长达1e9，开不了这么大的dp数组。对于数据范围较大导致暴空间，我们的一个处理方法就是离散化。但是这里需要怎么离散化呢？
看了大佬的题解(膜拜一下orz)，由于s和t可能远小于l，因此，猜想存在这样一种情况：当距离D大到一定程度之后，我们都可以移动到任意一个距离d(d>D)。这里贴个大佬的题解
https://www.luogu.com.cn/problem/solution/P1052
然后状态转移方程：
i为当前位置，j表示向前移动j个位置的结果。

完整代码

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
const int maxn=90*105;
int l,s,t,m;
vector<int> stone;
int mark[maxn];
int dp[maxn];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    clock_t c1 = clock();
    //===========================================================
    read(l),read(s),read(t),read(m);
    rep(i,1,m){
        int t;
        read(t);
        stone.push_back(t);
    }
    if(s==t){
        int ans=0;
        rep(i,0,stone.size()-1){
            if(stone[i]%s==0) ans++;
        }
        write(ans);
        return 0;
    }
    int pre=0;
    stone.push_back(0);
    sort(stone.begin(),stone.end());
    rep(i,1,stone.size()-1){
        if(stone[i]-stone[i-1]<s*t){
            pre=pre+stone[i]-stone[i-1];
            mark[pre]=1;
        }
        else{
            pre=pre+s*t;
            mark[pre]=1;
        }
    }
    memset(dp,0x7f,sizeof(dp));
    dp[0]=0;
    int l=pre+s*t;
    rep(i,1,l){
        rep(j,s,t){
            if(i-j>=0){
                if(mark[i]) dp[i]=min(dp[i],dp[i-j]+1);
                else dp[i]=min(dp[i],dp[i-j]);
            }
        }
    }
    int ans=INT32_MAX;
    rep(i,pre,l){
        ans=min(ans,dp[i]);
    }
    write(ans);
    //===========================================================
    std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}