题解 | #[NOIP2005]过河#

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e6+7;
int stone[107], now[107];
int vis[maxn], dp[maxn];

int main() {
    int l;
    cin>>l;
    int s, t, m;
    cin>>s>>t>>m;
    for (int i=1;i<=m;i++) {
        cin>>stone[i];
    }
    sort(stone+1, stone+1+m);
    //如果跳跃的距离固定的话可以直接遍历判断
    if (s==t) {
        int ans = 0;
        for (int i=1;i<=m;i++) {
            if (stone[i]%s==0) {
                ans++;
            }
        }
        cout<<ans<<endl;return 0;
    }
    //如果跳跃的距离不固定的话在这里使用区间离散化压缩的方式缩小所需要的空间。
    now[0] = 0;
    for (int i=1;i<=m;i++) {
        int cha = stone[i] - stone[i-1];
        if (cha>s*t) cha = s*t;
        now[i] = now[i-1] + cha;
        vis[now[i]] = 1;
    }
    l = now[m] + s*t;
    memset(dp, 127, sizeof(dp));
    dp[0] = 0;
    for (int i=1;i<=l;i++) {
        for (int j=s;j<=t;j++) {
            if (i>=j) {
                dp[i] = min(dp[i], dp[i-j]+vis[i]);
            }
        }
    }
    cout<<dp[l];
    return 0;
}