【每日一题】 过河 (dp / 数据压缩)

Solution
题意:
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
范围：
st 属于[1,10], 石头数量<=100, L<=1e9
思路：
很明显的dp题，dp[i]维护到达 i 点的最少步数：

但是要考虑到木板的范围高大 1e9 ，就需要离散化
因为 st 范围较小，所以我们可以把[1,10]的公倍数求出来，2520，即只要距离超过了2520就可以由[1,10]构造出来。
那么我们可以先对石头排序，然后求出他们相邻的距离，对2520取模，把数据压缩一下。
在枚举的时候我们可以直接把离散后最后的一块石头当成终点，然后枚举1 ~ 终点+t 的每个点，再枚举s~t,dp的方程是：

最后的话，因为题目说明跨过终点也算到达终点，所以ans要在 终点 ~ 终点+t 之间取 min 。
备注：因为我们是枚举每个点以及枚举s~t，所以不用考虑s==t的情况。

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e6+5;

ll a[manx],b[manx],c[manx],dp[manx];

int main(){
    io;
    ll l,s,t,m;   cin>>l>>s>>t>>m;
    for(int i=1;i<=m;i++) cin>>a[i];
    sort(a+1,a+1+m);
    for(int i=1;i<=m;i++) b[i]=(a[i]-a[i-1])%2520;
    for(int i=1;i<=m;i++) a[i]=a[i-1]+b[i],c[a[i]]=1;
    l=a[m];
    memset(dp,inf,sizeof(dp)); dp[0]=0;
    for(int i=1;i<=t+l;i++){
        for(int j=s;j<=t;j++)
            if(i>=j) dp[i]=min(dp[i],dp[i-j]+c[i]);
    }
    ll ans=1e18;
    for(int i=l;i<=t+l;i++) ans=min(ans,dp[i]);
    cout<<ans;
    return 0;
}