题意

有一个青蛙过桥，桥上有一些石头，桥长L，青蛙每次能跳[s,t]间的一个距离，问青蛙跳过桥最少才到的石头数

输入描述

第一行有一个正整数L（1<=L<=1e9），表示独木桥的长度。
第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1<=S<=T<=10，1<=M<=100。
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。
所有相邻的整数之间用一个空格隔开。

输出描述

只包括一个整数，表示青蛙过河最少需要踩到的石子数。

思路

很明显这个题目要用dp来解决，有石头的时候就是dp[i]=min(dp[i],dp[i-j]+1)   s<=j<=t 没有石头的时候dp=[i]=min(dp[i],dp[i-j])    s<=j<=t.然后看这个数据桥长1e9，而石头的数目不超过100，很明显要使用离散化（ps：菜鸡离散化不是很会用，只会依葫芦画瓢，我太难了）

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100001];
ll stone[101];
bool vis[100001]; //记录离散化之后石头的位置
void chushi(){
    for(ll i=0;i<10001;++i)
        dp[i]=0x3f;
}
int main(void){
    ios::sync_with_stdio(false);
    ll l,s,t,m;
    cin>>l>>s>>t>>m;
    chushi();
    memset(vis,0,sizeof(vis));  //初始化dp数组和石头的位置
    for(ll i=1;i<=m;++i)
        cin>>stone[i];
    sort(stone,stone+m+2);
    ll ide=0;   //离散化处理
    for(ll i=1;i<=m+1;i++){
        if(stone[i]-stone[i-1]<=t*s)
            ide+=stone[i]-stone[i-1];
        else
            ide+=(stone[i]-stone[i-1])%t+t;
        vis[ide]=true;
    }
    dp[0]=0;
    for(ll i=1;i<=ide+t;i++)
        for(ll j=s;j<=t;j++)
            if((i-j)>=0)
                dp[i]=min(dp[i],dp[i-j]+vis[i]);
    ll ans=0x3f;
    for (ll i=ide;i<=ide+t;i++)
        ans=min(ans,dp[i]);
    cout<<ans;
    return 0;
}
/*
10
2 3 5
2 3 5 6 7

2
*/