思路与算法

S=T时落点固定，直接数可整除石子；否则对长无石子间隔做有证明的状态稳定压缩，再按步长S..T求最少踩石数，并枚举越过终点的最后落点。

正确性说明

S<T时可用S和S+1。任意d>=S(S-1)，写d=qS+r，因q>=r，故d=(q-r)S+r(S+1)可达。对空段起点前最后T个DP状态中的最小代价g，从其所在位置出发，足够远的全部空位置都能以g到达，也不可能低于g。因此经过S(S-1)+T个空位置后整个最后T状态窗等于g；截断到更大的B保持下一石子前状态完全相同。压缩后线性DP转移覆盖所有合法最后一步，终点至终点+T-1取小允许跳过桥尾。

复杂度

压缩上界B=S²+2T+1，长度O(MB)；O(M log M+MBT)时间、O(MB+T)空间，含标记和DP初始化。

易错点

不把S=T也按固定间隔压缩；起点终点无石子，终点之后也无新增石子。压缩常数须有状态稳定证明。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int L, s, t, m;
    cin >> L >> s >> t >> m;
    vector<int> a(m);
    for (int &v : a)
        cin >> v;
    sort(a.begin(), a.end());
    if (s == t) {
        int ans = 0;
        for (int x : a)
            ans += x % s == 0;
        cout << ans << "\n";
        return 0;
    }
    a.push_back(L);
    int cap = s * s + 2 * t + 1, last = 0, pos = 0;
    vector<int> stone;
    for (int i = 0; i <= m; i++) {
        pos += min(cap, a[i] - last);
        last = a[i];
        if (i < m)
            stone.push_back(pos);
    }
    vector<int> mark(pos + t), dp(pos + t, 1000000);
    for (int x : stone)
        mark[x] = 1;
    dp[0] = 0;
    for (int x = 1; x < pos + t; x++)
        for (int j = s; j <= t && j <= x; j++)
            dp[x] = min(dp[x], dp[x - j] + mark[x]);
    cout << *min_element(dp.begin() + pos, dp.end()) << "\n";
}