算法

(动态规划,数学) $O(mT^3)$

如果不考虑 $L$ 的范围，那么就是一道简单的DP问题：

• 状态表示 f[i] 表示走到位置 i，踩到的石头个数的最小值；
• 状态计算 f[i] = min(f[j]) + w[i], 其中 w[i] 表示第 i 个位置是否有石头，i - j 在 S 到 T 之间。

那么当 $L$ 很大时该怎么办呢，我们发现虽然 $L$ 是 $10^9$ 级别，但石头总数很少，最多只有 $100$ 个，因此两个石头之间可能有很长的“空隙”。

接下来分两种情况讨论：

• 如果 S == T，那么走法唯一，石头位置是 S 整数倍的一定会被踩，否则一定不会被踩，直接遍历一遍所有石头即可；
• 如果 S != T，那么我们考虑不能被 S, S+1, S+2, ..., T 所表示的数有哪些，由 AcWing 525. 小凯的疑惑这道题目的结论，如果我们只用两个相邻的数 $p, q$，那么不能被表示的数的最大值是 $(p - 1)(q - 1) - 1$，因此所有大于等于 $(p - 1)(q - 1)$ 的数一定可以被 $p, q$ 表示出来，当 $p = 9, q = 10$ 时取到最大值，此时 $(p - 1)(q - 1) = 72$，因此所有大于等于72的数，一定可以被 S, S+1, S+2, ..., T 表示出来。当第一次越过第 $i$ 个石头时，青蛙的位置一定在该石头右侧十步以内，如下图所示左侧棕色线段处；当即将跳过第 $i + 1$ 个石头时，青蛙一定在第 $i + 1$ 个石头左侧十步以内，如下图右侧棕色线段处。那么当中间部分的长度大于100时，可以从左侧棕色线段内的任意一点，跳到右侧棕色线段内的任意一点，此时我们可以将线段的长度缩短为100，得到的结果是等价的。那么此时最多只会用到 $100 * 100 = 10000$ 个位置，复杂度可以接受了。

时间复杂度

每个两个石头之间最多会添加 $100$ 个位置，因此总共最多有 $10000$ 个状态，计算每个状态最多需要 $10$ 次计算，因此总计算量是 $10^5$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10020;

int n, S, T, m;
int stones[N];
int w[N], f[N];

int main()
{
    scanf("%d%d%d%d", &n, &S, &T, &m);

    if (S == T)
    {
        int res = 0;
        while (m -- )
        {
            int x;
            scanf("%d", &x);
            if (x % S == 0) res ++ ;
        }
        printf("%d\n", res);
    }
    else
    {
        for (int i = 0; i < m; i ++ ) scanf("%d", &stones[i]);
        sort(stones, stones + m);

        int last = 0, k = 0;
        for (int i = 0; i < m; i ++ )
        {
            for (int j = 0; j < min(stones[i] - last, 100); j ++ )
                w[ ++ k] = 0;
            w[k] = 1;
            last = stones[i];
        }
        for (int i = 1; i <= k + 10; i ++ )
        {
            f[i] = 1e9;
            for (int j = S; j <= T; j ++ )
                if (i - j >= 0)
                    f[i] = min(f[i], f[i - j] + w[i]);
        }
        int res = 1e9;
        for (int i = k + 1; i <= k + 10; i ++ )  res = min(res, f[i]);

        printf("%d\n", res);
    }

    return 0;
}