过河（离散化dp）

题目：

青蛙要从数轴0跳到L（L最大1e9）。每次跳跃步长在[s,t]区间（s、t≤10）。数轴上有m（m最大100）个石头。问青蛙最少跳上的石头数量。

做法：

表示从0跳到i最少跳上的石头数量。枚举所有步长转移即可： 表示当前位置是否是石头。
然而发现L很大，数组开不了这么大，所以我们需要对石头间的距离进行一下处理。
发现只要，超过一定距离是必达的。
什么意思呢？比如两个石头间距离是100。
我们穷举所有情况发现必达：









故只要相邻两块石头距离≥100，我们直接模100即可。
然后就直接做dp就行了。
而当，做特判，每颗石头模s看是否等于0即可。

代码；

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 110;
const int M = 2e4 + 7;
const int inf = 0x3f3f3f3f;
int l, s, t, m, a[N], stone[M], dp[M];
void solve1(void){
    int cnt = 0;
    for (int i = 1; i <= m; ++i){
        if (a[i]%s == 0) cnt++;
    }
    cout << cnt << endl;
}
void solve2(void){
    int fix = 100;
    for (int i = 1; i <= m; ++i){
        a[i] = a[i-1]+(a[i]-a[i-1])%fix;
        stone[a[i]] = 1;
    }
    memset(dp, inf, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= a[m]+fix; ++i){
        for (int j = s; j <= t; ++j){
            if (i-j < 0) continue;
            dp[i] = min(dp[i], dp[i-j]+stone[i]);
        }
    }
    int ans = inf;
    for (int i = a[m]; i <= a[m]+fix; ++i){
        ans = min(ans, dp[i]);
    }
    cout << ans << endl;
}
int main(void){ 
    IOS;
    cin >> l >> s >> t >> m;
    for (int i = 1; i <= m; ++i) cin >> a[i];
    sort(a+1, a+m+1);
    if (s == t){
        solve1();
    }else{
        solve2();
    }
    return 0;
}