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

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

对于30%的数据，L <= 10000；
对于全部的数据，L <= 10^9。

输入格式

输出格式

样例输入1

102 3 52 3 5 6 7

样例输出1

2

1s

 1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<cstdlib> 7 using namespace std; 8 long long l,s,t,m; 9 long long map[1000005];10 long long k[1000005];11 long long pos[105];12 long long ans[1000005];13 long long min(long long x,long long y)14 {15     if(x<y)return x;16     return y;17 }18 int main()19 {20     for(int i=0;i<=1000004;i++)21     ans[i]=99999999;22     scanf("%I64d%I64d%I64d%I64d",&l,&s,&t,&m);23     long long mod=s*t;24     for(int i=1;i<=m;i++)25     scanf("%I64d",&pos[i]);26     sort(pos+1,pos+m+1);27     int temp=0;28     for(int i=1;i<=m;i++)29     {30         long long cha=pos[i]-pos[i-1];31         long long qwe=cha;32         cha%=mod; qwe/=mod;33         temp+=cha;34         if(qwe!=0)35         temp+=mod;36         k[temp]=1;37     }38     temp+=s*t;39     if(s==t)40     {41         long long u=0;long long v=s;int an=0;42         while(u<=temp)43         {44             u+=v;45             if(k[u])an++;46         }47         printf("%d",an);48         exit(0);49     }50     for(int i=0;i<=s-1;i++)51     ans[i]=0;52     for(int i=s;i<=temp;i++)53     {54         for(int j=s;j<=t;j++)55         {56             if(i-j<0)break;57             if(i-j>0&&i-j<s)continue;58             ans[i]=min(ans[i-j]+k[i],ans[i]);59         }60     }61     printf("%I64d",ans[temp]);62 }