题解 | 过河

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> stones_flag(200000,0);
int main() {
    int L,S,T,M;
    cin>>L;
    cin>>S>>T>>M;
    vector<int> stones(M,0);
    for(int i=0;i<M;i++){
        cin>>stones[i];
    }
    sort(stones.begin(),stones.end());
    //首先计算S==T的情况
    if(S==T){
        int sum=0;
        for(int i=0;i<M;i++){
            if(stones[i]%S==0){
                sum++;
            }
        }
        cout<<sum;
        return 0;
    }
    //由于L过长，应当压缩空间，便于线性dp
    for(int i=0,last=0,offset=0;i<M;i++){
	  //stones[i]-last表示前后两个石子的距离
        if(stones[i]-last>100)
        offset+=stones[i]-last-100;
        last=stones[i];
        stones[i]-=offset;
    }
    //将压缩空间的石子位置设置为1，告诉此处有石子
    for(int i=0;i<M;i++){
        stones_flag[stones[i]]=1;
    }
    int L1=stones[M-1]+10;
    vector<int> dp(L1+1,0);
    for(int i=1;i<L1+1;i++){
        dp[i]=110;
        for(int j=S;j<T+1 && i-j>=0;j++){
            dp[i]=min(dp[i],dp[i-j]+stones_flag[i]);
        }
    }
    cout<<dp[L1];
    return 0;

}
// 64 位输出请用 printf("%lld")