题解 | 过河

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long L; int S, T, M;
    cin >> L;
    cin >> S >> T >> M;
    vector<long long> a(M);
    for (int i = 0; i < M; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    // 特例：固定步长
    if (S == T) {
        int cnt = 0;
        for (auto x : a) if (0 < x && x < L && x % S == 0) ++cnt;
        cout << cnt << '\n';
        return 0;
    }
    // 构造含起终点的坐标序列
    vector<long long> b; b.reserve(a.size() + 2);
    b.push_back(0);
    for (auto x : a) if (0 < x && x < L) b.push_back(x);
    b.push_back(L);
    // 坐标压缩：把空隙> T 的部分收缩为 T
    vector<int> pos; pos.reserve(b.size());
    pos.push_back(0);
    for (size_t i = 1; i < b.size(); ++i) {
        long long d = b[i] - b[i - 1];
        pos.push_back(pos.back() + (int)min<long long>(d, T));
    }
    int N = pos.back();
    vector<int> has(N + 1, 0);
    for (size_t i = 1; i + 1 < b.size(); ++i) has[pos[i]] = 1;
    const int INF = 1e9;
    vector<int> dp(N + 1, INF);
    dp[0] = 0;
    // 朴素 DP（区间长度 ≤ T ≤ 10）
    for (int x = 1; x <= N; ++x) {
        int best = INF;
        int Lwin = max(0, x - T), Rwin = x - S;
        for (int k = Lwin; k <= Rwin; ++k) best = min(best, dp[k]);
        if (best < INF) dp[x] = best + has[x];
    }
    cout << dp[N] << '\n';
    return 0;
}