【题解】过河

首先这个题DP应该是挺容易看出来的，就是一个线性的东西，后面的可以从前面的转移。

然后既然想到了DP，可以决定一下DP的状态，很显然可以定dp[i]为到位置i的时候最少踩多少个石子。
再然后就是转移方程了，对于s<=j<=t,并且i>=j,dp[i]=min(dp[i],dp[i-j]+vis[i]])，其中vis[i]表示i号位是不是一个石子。

这样DP部分是完成了，但是有一个很有意思的点就是，这个l好大，竟然到了1e9。可是呢，s,t,m这些都好小，最大才100。

做过离散化相关的题的人都会发现，应该是需要离散化一下了。
如果不懂离散化也没问题，下面也能讲得清楚：

假如你在0号位，下一个石子在55号位，t是10。那可以发现肯定是这样跳的：0->10->20->30->40->50，先跳到50再说，因为0到50这一段相当于没用的，只有50到55这一段才会发生DP的状态转移。
因此：对于距离大于t的石子，可以把距离s对t取模，也就是(s%t)+t（+t是因为两个点不能重复，取模(s%t)有可能变成0）。

经过这样处理以后，这个距离就短多了，因为t最大就是10，m是100，撑死了也就是100*10=1000。
最后记得要多跑一点，因为只要大于等于l，所以转移要转移到l+t-1那个位置。（为了贪方便我就直接+100了）。
下面是代码：

#include<bits/stdc++.h>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int dp[maxn],a[maxn],vis[maxn];

int main(){
    int l;
    scanf("%d",&l);
    int s,t,m;
    scanf("%d%d%d",&s,&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",a+i);
    }
    sort(a+1,a+1+m);
    a[0]=0;a[m+1]=l;int tmp=0;
    for(int i=1;i<=m+1;i++){
        if(a[i]-a[i-1]>t){
            tmp+=(a[i]-a[i-1])%t+t;
        }
        else tmp+=a[i]-a[i-1];
        vis[tmp]=1;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=tmp+100;i++){
        for(int j=s;j<=t;j++){
            if(i>=j) dp[i]=min(dp[i],dp[i-j]+vis[i]);
        }
    }
    int ans=inf;
    for(int i=tmp;i<=tmp+100;i++){
        ans=min(dp[i],ans);
    }
    printf("%d",ans);
    return 0;
}