过河

离散化+dp

观察数据范围，桥的距离很长，但是石子很少，所以中间会存在相隔很远的石子，所以我们要对他们的中间的路径进行压缩，也就是离散化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int l;
int s,t,m;
int dp[20005]; 
int vis[20005]; //是否有石子

int main()
{
    scanf("%d",&l);
    scanf("%d%d%d",&s,&t,&m);
    vector<int> v(m);
    for(auto &i:v)
        scanf("%d",&i);
    v.push_back(0);
    v.push_back(l); 
    sort(v.begin(),v.end());
    vector<int> vv(v);
    for(int i=1;i<(int)vv.size();i++)
    {
        //离散化
        if(vv[i]-vv[i-1]>100)
            v[i]=v[i-1]+100+(vv[i]-vv[i-1]-100)%t;
        else
            v[i]=v[i-1]+vv[i]-vv[i-1];
    }
    for(int i=1;i<(int)v.size()-1;i++)
        vis[v[i]]=1;
    memset(dp,0x3f,sizeof dp);
    dp[0]=vis[0];
    for(int i=s;i<=v.back()+100;i++)
    {
        for(int j=s;j<=t;j++)
        {
            if(j<=i)
                dp[i]=min(dp[i],dp[i-j]+vis[i]);
        }
    }

    printf("%d\n",*min_element(dp+v.back(),dp+v.back()+100));
    return 0;
}