算法知识点: 动态规划，数学

复杂度：

解题思路：

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

  • 状态表示 表示走到位置 ，踩到的石头个数的最小值；
  • 状态计算 , 其中 表示第 个位置是否有石头， 在 到 之间。

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

接下来分两种情况讨论：

  • 如果 ，那么走法唯一，石头位置是 整数倍的一定会被踩，否则一定不会被踩，直接遍历一遍所有石头即可；
  • 如果 ，那么我们考虑不能被 所表示的数有哪些，如果我们只用两个相邻的数 ,那么不能被表示的数的最大值是 ，因此所有大于等于 的数一定可以被 表示出来，当 时取到最大值，此时，因此所有大于等于72的数，一定可以被 表示出来。当第一次越过第个石头时，青蛙的位置一定在该石头右侧十步以内；当即将跳过第 个石头时，青蛙一定在第个石头左侧十步以内。那么当中间部分的长度大于100时我们可以将线段的长度缩短为100，得到的结果是等价的。那么此时最多只会用到 个位置，复杂度可以接受了。

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;
}



另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ