30pts $O(tL)$

动态规划:状态表示f[i]表示走到位置i的最少的石头的数量,w[i]表示$i$这个位置上的石头上是否有石头 .

$f[i]=min\{f[i-s],f[i-s+1]...f[i-t]\}+w[i]$

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+20;
int f[N]; //f[i]表示走到第i个位置的经过的最少的石头的数目
int w[N]; //w[i]=1表示i这个位置上有石头
int main()
{
    int L;
    int s,t,m;
    cin>>L>>s>>t>>m;
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        w[x]=1; //记录这个位置有石头
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=L+t;i++) //枚举走到的点
    {
        for(int k=i-t;k<=i-s;k++) //可以从哪个位置过来
        {
            if(k>=0) //合法距离
                f[i]=min(f[i],f[k]+w[i]);
        }
    }
    int res=100000;
    for(int i=L;i<=L+t;i++) //枚举跳过后跳到的位置
    {
        res=min(res,f[i]);
    }
    cout<<res;
    return 0;
}

100pts $O(100mt)$

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

-如果 $S= T$，那么走法唯一，石头位置是 $S$ 整数倍的一定会被踩，否则一定不会被踩，直接遍历一遍所有石头即可;

-如果 $S!=T$，那么我们考虑不能被 $S，S+1，S+2,….,T$所表示的数有哪些，

如果我们只用两个相邻的数$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 个位置，复杂度可以接受了。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=10020;
int n,S,T,m;
int stones[N];
int w[N],f[N];
int main()
{
    cin>>n>>S>>T>>m;
    if(S==T) //特殊点的判定
    {
        int res=0;
        while(m--)
        {
            int x;
            cin>>x;
            if(x%S==0)
            {
                res++;
            }
        }
        cout<<res;
    }
    else
    {
        for(int i=0;i<m;i++)
        {
            cin>>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];//更新上一个石头的距离
        }
        memset(f,0x3f,sizeof f);//初始化无穷大
        f[0]=0;//初始化距离
        for(int i=1;i<=k+10;i++) //枚举映射以后的每个位置
        {
            for(int j=i-T;j<=i-S;j++) //枚举从哪个位置来
            {
                if(j>=0)
                {
                    f[i]=min(f[i],f[j]+w[i]);
                }
            }
        }
        int res=1000000;
        for(int i=k;i<=k+10;i++) //枚举终点位置
        {
            res=min(res,f[i]);
        }
        cout<<res;
    }
    return 0;
}