题目描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

输入描述:

第一行有一个正整数，表示独木桥的长度。
第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中。
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。
所有相邻的整数之间用一个空格隔开。

输出描述:

只包括一个整数，表示青蛙过河最少需要踩到的石子数。

示例1

输入
10
2 3 5
2 3 5 6 7
输出
2

备注

对于30%的数据，；
对于全部的数据，。

解答

我们用表示到第i个位置时，最少踩到的石头数，falg[i]表示第i个位置有没有石头。
那么可以影响到第i个位置的就是i-s到i-t;
所以可以得到转移方程：
但是看下范围：
10^9显然会超出空间，但是另外三个S，T，M都很小。
仔细思考便可以发现，因为i点的值会影响到i+s至i+t，i+s至i+t会影响到i+2s到i+2t，i+2s到i+2t会影响到i+3s到i+3t...以此类推，当(k-1)小于等于kt时，前后两段范围重叠，所以会趋于稳定，而K，S的最小公倍数为90,所以当两个石头之间距离超出90时，可以将其压缩为90（90以后的f值与90相同），这时数组大概就只有90×100=9000了。
注意：因为青蛙的最后一跳不一定正好落在终点，有可能超出终点，所以答案是终点到终点+t-1中间的最小值。
最后是一份丑陋的代码： 
#include<bits/stdc++.h>
using namespace std;
bool cl[10020];
int main()
{
    int f[10020],p=0,s,t,l,n,k,a[10020],len[10020],i,ans=0;
    scanf("%d%d%d%d",&l,&s,&t,&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    if(s==t)
      {
    for(i=1;i<=n;i++)
            if(a[i]%t==0) ans++;
                 else continue;
    cout<<ans;
      }
       else
         {
       p=min(a[1],90);
       len[1]=p;
       cl[p]=1;
       for(i=2;i<=n;i++)
        { 
        k=min(a[i]-a[i-1],90);      
              p+=k;
          cl[p]=1;
          len[i]=p;
             }
       p+=min(l-a[n],90);
       for(i=1;i<=p+9;i++)
           {
             f[i]=3000000;
              for(int j=s;j<=t;j++)
              if(i-j>=0) f[i]=min(f[i],f[i-j]+cl[i]);
             }
         ans=9000000;
       for(i=p;i<=p+9;i++)
           ans=min(ans,f[i]);
           cout<<ans;
     }
           return  0; 
}


来源：_Lemon_