离散化dp

题目描述：

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

思路：

很显然是dp

状态是到达位置 i 时踩的石头的数量最少值

dp[i] = min(dp[i], dp[i - j] + vis[i])

其中vis[i] 指的是位置 i 是否有石头，有则为1，无则为0

再猫一眼题目范围，L<=1e9，不仅数组开不下，时间上也饶不了你

再猫一眼，发现石头的数量很少，暗示我们可以进行离散化，常见的离散化是通过map进行映射，但是这个题离散化的是石头间的距离

对于两个石头x，y，如果他们的距离大于lcm(s, t)时，则大于lcm(s,t)的所有点都可以到达，这个是可以证明的不过我不会证o(︶︿︶)o

还可以再简单一点，就是如果你懒得写lcm的板子的话，那直接让大于s * t的点之间的距离等于s * t即可

对于s = t的情况要进行特判

还有就是因为跳过了终点也算过了，那我们就让循环的右边界为st[n] + s * t

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！

int l, n, s, t;
int tr[MAX];
int vis[MAX];
int st[MAX];
int dp[MAX];

int main(){
    cin>>l>>s>>t>>n;
    for(int i = 1; i <= n; ++i)cin>>tr[i];
    sort(tr + 1, tr + 1 + n);
    if(s == t){
        int cnt = 0;
        for(int i = 1; i <= n; ++i)if(tr[i] % s == 0)++cnt;
        cout<<cnt<<endl;
        return 0;
    }
    int k = s * t;
    st[0] = 0;
    for(int i = 1; i <= n; ++i){
        if(tr[i] - tr[i - 1] >= k)st[i] = st[i - 1] + k;
        else st[i] = st[i - 1] + tr[i] - tr[i - 1];
        vis[st[i]] = 1;
    }
    int r = st[n] + k;
    mem(dp, inf);
    dp[0] = 0;
    for(int i = 1; i <= r; ++i){
        for(int j = s; j <= t; ++j){
            if(i >= j)dp[i] = min(dp[i], dp[i - j] + vis[i]);
        }
    }
    int ans = 1e9;
    for(int i = st[n]; i <= r; ++i)ans = min(dp[i], ans);
    cout<<ans<<endl;
    return 0;
}