#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
int loc[500],l,s,t,m;
int nown,p;
int f[1000000],ans=1000;
int stone[1000000];
int main()
{
scanf("%d%d%d%d",&l,&s,&t,&m);
for (int i=1;i<=m;i++)
scanf("%d",&loc[i]);
sort(loc+1,loc+m+1);
memset(f,2,sizeof(f));
f[0]=0;
for (int i=1;i<=m;i++)
{

int k;
k=(loc[i]-loc[i-1])%(s*t);
if (((loc[i]-loc[i-1])/(s*t))>=1) k+=s*t;
stone[nown+k]=1;
for (int u=nown;u<=nown+k;u++)
for (int j=s;j<=t;j++)
if (u-j>=0)
{
if (stone[u]==1)
f[u]=min(f[u],f[u-j]+1);
else f[u]=min(f[u],f[u-j]);
}
nown+=k;
}
for (int i=nown-t+1;i<=nown;i++)
ans=min(ans,f[i]);
cout<<ans;
return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int L,s,t,m,ans;
int a[110];//保存石子的位置 
int f[11000]={0};//f[x]表示青蛙跳到位置i最少踏的石子数 
int stone[11000]={0};//stone[x]表示位置x是否是石子，0表示不是，1表示是
void solve()
{
    //十亿数据过大 进行压缩  
    int d(0),k=s*t,x;  //d表示累加平移量，k表示s和t的公倍数
    for (int i=1;i<=m+1;i++)
    {
        x=a[i]-d-a[i-1];  //x表示第i个石子和第i-1个石子的距离
        if (x>k) d+=x-k;  //超过公倍数部分用作平移
        a[i]=a[i]-d;
        stone[a[i]]=1;  //标记平移后位置是石子
    }
    stone[a[m+1]]=0; //桥尾不是石子
    f[0]=0;
    for (int i=1;i<=a[m+1]+t-1;i++)  //考查桥上到桥尾的所有位置
    {
        f[i]=105;  
        for (int j=s;j<=t;j++) //在i的前一个位置中找一个经历石子最少的
           if (i>=j) f[i]=min(f[i],f[i-j]);
        f[i]+=stone[i];  //加上当前位置石子数
    }
    ans=101;
    for (int i=a[m+1];i<=a[m+1]+t-1;i++)  //在跳过桥后的所有位置中找一个最小值
        ans=min(ans,f[i]);
    cout<<ans<<endl;
}
int main()
{
    cin>>L>>s>>t>>m;
    ans=0;
    a[0]=0; a[m+1]=L;
    for (int i=1;i<=m;i++) cin>>a[i];
    sort(a+1,a+m+1);  //对桥中间石子位置排序
    if (s==t) {  //这种情况只需考查石子是否是石子的倍数即可
        for (int i=1;i<=m;i++)
            if (a[i]%s==0)
                ans++;
        cout<<ans<<endl;  
    }
    else solve();
    return 0;
}

题目给的石子位置是乱序的，要排序= =

状压dp，把石子的距离模2520(lcm(1-10))即可
```c++
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MaxM=100;
const int MaxL=2520;

int L,S,T,M,A[MaxM+1],Stone[MaxM*MaxL+1],F[MaxM*MaxL+1];

void init()
{
cin>>L;
cin>>S>>T>>M;
for(int i=1;i<=M;i++)
cin>>A[i];
sort(A+1,A+1+M);
}

void compress()
{
for(int i=1;i<=M;i++)
{
A[i]=A[i-1]+(A[i]-A[i-1])%MaxL;
Stone[A[i]]=1;
}
}

int dp()
{
memset(F,127,sizeof(F));
F[0]=0;
for(int i=S;i<=MaxM*MaxL;i++)
for(int j=S;j<=T;j++)
if(i>=j)
F[i]=min(F[i],F[i-j]+Stone[i]);
return F[MaxM*MaxL];
}

int main()
{
init();
compress();
cout<<dp()<<'\n';
}
```

第一次瞎yy出来一种算法，但在90分磕了半天....
30%的方法很容易想到，但是70%需要把两石头间的距离压缩（比如说1000000可以压缩成200）。但是这就出现了一个问题，当s==t时，石头与石头间的路并不一定都被覆盖到（也就是我在90分磕半天的原因orz），所以需要特殊处理。（因为此题最大跨度是10，所以压缩成200即可覆盖当s!=t时石头间的路）
如果有疑问可以探讨一下，因为我采取的数字（200）并不是通过严格计算证明的。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define inf (1 << 30)
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define dwn(i, x, y) for (int i = x; i >= y; --i)

using namespace std;

int l;
int s, t, m;
int val[105];
int b[30005], f[30005];

int main(int argc, const char *argv[]) {
scanf("%d%d%d%d", &l, &s, &t, &m);
for (int i = 1; i <= m; ++i) scanf("%d", &val[i]);
if (s == t) {
int ans = 0;
rep(i, 1, m) if (val[i] % s == 0) ++ans;
printf("%d\n", ans);
return 0;
}
val[0] = 0;
sort(val, val + m + 1);
int su[105] = {};
rep(i, 1, m) su[i] = val[i] - val[i - 1];
rep(i, 1, m) if (su[i] >= 200) su[i] = 200;
rep(i, 1, m) {
val[i] = val[i - 1] + su[i];
b[val[i]] = 1;
}
rep(i, 1, val[m]) {
f[i] = inf;
dwn(j, i - s, i - t) {
if (j < 0) break;
f[i] = min(f[i], f[j] + b[i]);
}
}
int ans = inf;
dwn(i, val[m], val[m] - 20) {
if (i < 0) break;
if (i + t > val[m] && f[i] < ans) ans = f[i];
}
printf("%d\n", ans);
return 0;
}
后来发现s与t是倍数关系时也不行，看来这题AC纯属瞎蒙的......

感谢**cjoierlucy**；
感谢**希望之光**；

编译通过...
测试数据 #0: Accepted, time = 234 ms, mem = 392192 KiB, score = 10
测试数据 #1: Accepted, time = 343 ms, mem = 392192 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 392192 KiB, score = 10
测试数据 #3: Accepted, time = 343 ms, mem = 392188 KiB, score = 10
测试数据 #4: Accepted, time = 359 ms, mem = 392192 KiB, score = 10
测试数据 #5: Accepted, time = 328 ms, mem = 392192 KiB, score = 10
测试数据 #6: Accepted, time = 359 ms, mem = 392192 KiB, score = 10
测试数据 #7: Accepted, time = 343 ms, mem = 392192 KiB, score = 10
测试数据 #8: Accepted, time = 375 ms, mem = 392192 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 392192 KiB, score = 10
Accepted, time = 2684 ms, mem = 392192 KiB, score = 100

压缩+普通动规

思路跟楼上一样，具体见代码，一开始忘了压缩开头和结尾的路径，结果RE了无数次
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int s, t, m, tot = 0, ans = 0;
long long l;
int vis[11000] = {0};
int sto[110] = {0};
int f[11000] = {0};

int main ()
{
//freopen ("in.txt", "r", stdin);
cin >> l >> s >> t >> m;
for (int i = 0; i < m; i++) cin >> sto[i];
sort (sto, sto + m);
if (s == t) {
for (int i = 0; i < m; i++) {
if (!(sto[i]%s)) ans++;
}
cout << ans;
return 0;
}
int e;
if (sto[0] > 100) vis[tot = 100] = 1;
else vis[tot = sto[0]] = 1;
for (int i = 1; i < m; i++) {
if ((e = sto[i] - sto[i-1]) > 100) { vis[tot += 100] = 1;}
else { vis[tot += e] = 1;}
}

for (int i = tot; i >= 0; i--) {
f[i] = 200;
for (int j = s; j <= t; j++) {
f[i] = min (f[i], f[i+j] + vis[i]);
}
}
cout << f[0];
return 0;
}
```

这是过河的缩进方法版

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
int a[105],l,s,t,m,b,c[10015],f[10015];
int main()
{
cin>>l>>s>>t>>m;
for(int i=1;i<=m;i++)
cin>>a[i];
if(s==t)
{
int e=0;
for(int i=1;i<=m;i++)
if(a[i]%s==0)
e++;
cout<<e;
return 0;
}
sort(a+1,a+m+1);
a[m+1]=l;
for(int i=1;i<=m+1;i++)
{
if(a[i]-a[i-1]>100)
b+=100;
else
b+=a[i]-a[i-1];
c[b]=1;
}
c[b]=0;
memset(f,1,sizeof(f));
copy(c+s,c+t+1,f+s);
for(int i=t+1;i<=b+t;i++)
f[i]=*min_element(f+i-t,f+i-s+1)+c[i];
cout<<*min_element(f+b,f+b+t+1);
return 0;
}

动规。。。。你们自己看吧 注意离散化
```
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100000+5
int sz[MAXN],a[MAXN],f[MAXN];
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int main()
{
int l,s,t,m;
cin>>l>>s>>t>>m;
memset(f,127,sizeof f);
for(int i=1;i<=m;++i)
a[i]=read();
if(s==t)
{
long long ans=0;
for(int i=1;i<=m;++i)
if(!(a[i]%s))
ans++;
cout<<ans;
return 0;
}
sort(a,a+m+1);
a[m+1]=l;
for(int i=0;i<=m;++i)
if(a[i+1]-a[i]>90)
a[i+1]=a[i]+(a[i+1]-a[i])%90;
for(int i=1;i<=m;++i)
sz[a[i]]=1;
for(int i=s;i<=t;++i)
if(sz[i])
f[i]=1;
else
f[i]=0;
for(int i=2*s;i<=a[m+1];++i)
{
for(int j=s;j<=t;j++)
{
if(j>i)break;
f[i]=min(f[i-j],f[i]);
}
if(sz[i])
f[i]++;
}
cout<<f[a[m+1]]<<endl;
}

tertet

自认为优化到底了，请大犇看看。

#include<cstdio>
#include<algorithm>
int l, s, t, m, *p;
int comp(const void *a, const void *b)
{
return (int)a - (int)b;
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &l, &s, &t, &m);
p = new int[m];
for (int i = 0; i < m; i++)
scanf("%d", p + i);
std::qsort(p, m, 4, comp);
if (s == t)
{
int ans = 0;
for (int i = 0; i < m; i++)
ans += int(p[i] % s == 0);
printf("%d", ans);
}
else
{
int k = (s == 1) ? 2 : s*(s - 1), mo = 0;
if (p[0] > k)
mo = p[0] - k, p[0] = k;
for (int i = 0; i < m - 1; i++)
{
p[i + 1] -= mo;
if (p[i + 1] - p[i]>k)
mo += p[i + 1] - p[i] - k, p[i + 1] = p[i] + k;
}
l -= mo;
if (l - p[m - 1] > k)
l = p[m - 1] + k;
int *q = new int[t + 1], x = 0;
for (int i = 1; i < t; i++)
q[i] = m;
q[0] = 0;
for (int i = 0; i < l + k; i++)
{
q[(i + t) % (t + 1)] = m;
for (int j = i + s; j <= i + t; j++)
if (q[j % (t + 1)] > q[i % (t + 1)])
q[j % (t + 1)] = q[i % (t + 1)] + int(i == p[x]);
if (x < m - 1 && i == p[x])
x++;
}
printf("%d", q[(l + k) % (t + 1)]);
delete[]q;
}
delete[]p;
return 0;
}

第一道动规题自己AC，庆贺~

首先说一下简单思想，用普普通通的DP一定是会超的，不管是时间还是空间，所以我们必须要想一想优化。

从题目我们能发现一个很重要的事情：石子数m和独木桥长度l相差的太多了，也就是说，相邻两个石子之间会存在着一大截的空地，达到这些空地，所经过石子数是一样的！（这里要重点思考一下，不然后面的讲解便无法进行）我们便能够从这一方面优化时间：当经过一个石子后，若有大于10个地点经过石子数是一样的，我们便可以直接跳到下一个石子处。（要先给石子的坐标排序，因为所给的石子坐标不是升序给的）这样便极大程度的优化了时间。

但同时，我们要思考，假如一开始就给你一大堆石子，让你走完之后存在一大段空地，那该怎么办呢？很简单，我们可以统计一下经过了多少石子，假如已经通过了所有石子，那么我们就可以对之后的i +s至i + t区域进行计算，排序求出最小值便能直接输出了，因为在之后的空地中，结果都一样啊~

同样的，假如一开始给你一大段空地，把石子放在最后，我们可以先统计经过空地的数目，假如大于10个，那就直接跳到第1个石子处就好啦！

说完了时间方面的优化，我们说说空间优化。假如要开一个10^9的数组。。。呵呵，评测机要和你说再见了！既然静态数组不能开那么大，那我们就开滚动数组！哼哼o(￣ヘ￣o#)。滚动数组我就不多说了，这是基础的数据类型，假如不会那就要重新看看算导了。不过我要提醒一点，在前100个空点要开一维数组算，因为会有走不到的地方，可以开BOOL数组来判断是否能走。

OK！讲解完毕！下面粘代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int l , s , t , m , i , j , stone[105] , temp = 0 , a1[105] , a[10] , count1;
bool f[105];
int main()
{
scanf ("%d%d%d%d" , &l , &s , &t , &m);
for (i = 0; i < m; i ++)
scanf ("%d" , &stone[i]);

if (s == t)
{
int ans = 0;
for (i = 0; i < m; i ++)
if (stone[i] % s == 0)
ans ++;
printf ("%d" , ans);
return 0;
}

sort (stone , stone + m);
f[0] = true;
for (i = 0; i < 100; i ++)
{
if (f[i])
{
if (i == stone[temp])
{
a1[i] += 1;
temp ++;
}
for (j = s; j <= t; j ++)
{
if (f[i + j])
a1[i + j] = min (a1[i + j] , a1[i]);
else
{
a1[i + j] = a1[i];
f[i + j] = true;
}
}
}
}

for (i = 90; i < 100;i ++)
a[(i - 90) % 10] = a1[i];
i = 100;
count1 = 0;
while (i < l)
{
a[i % 10] = a[(i - t) % 10];
for (j = s; j < t; j ++)
a[i % 10] = min(a[i % 10] , a[(i - j) % 10]);
if (i == stone[temp])
{
a[i % 10] ++;
temp ++;
}

if (temp == m)
{
int k = a[(i + 1 - t) % 10];
for (j = s; j < t; j ++)
k = min (k , a[(i + 1 - j) % 10]);
printf ("%d" , k);
return 0;
}

if (a[i % 10] == a[(i - 1) % 10])
count1 ++;
else
count1 = 0;
if (count1 == 10)
{
for (j = 0; j < 10; j ++)
a[j] = a[i % 10];
i = stone[temp] - 1;
}
i ++;
}
if (l < 100)
printf ("%d" , a1[l]);
else
printf ("%d" , a[l % 10]);
return 0;
}

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

using namespace std;

int stone[1000001],map[1000001],f[1000001];

//int ans;
int w=2000;
int l,s,t,m;
int p=0,k;/*
inline void findd(int a)
{
if(ans>w)return;
if(a>=p)
{
if(ans<w)w=ans;
return;
}
int i;
for(i=a+s;i<=a+t;++i)
{
if(map[i]==1)ans++;
findd(i);
if(map[i]==1)ans--;
}
return;
}
*/
int main()
{

scanf("%d%d%d%d",&l,&s,&t,&m);

int i,j;

for(i=1;i<=m;++i)
scanf("%d",&stone[i]);

sort(stone+1,stone+m+1);

for(i=1;i<=m;++i)
{
l=stone[i]-stone[i-1];
if(l%t==0)k=t;
else k=l%t+t;
if(l<k)k=l;
p+=k;
map[p]=1;
}
for(i=1;i<=p+t;++i)
{
w=200;
for(j=i-t;j<=i-s;++j)
{
if(j>=0&&f[j]<w)w=f[j];
}
/*for(j=i-t;j>=0&&j<=i-s;++j) //把j>=0放在循环头，有时候可能导致循环不进行（开始的时候）
{
if(f[j]<w)w=f[j];
}*/
f[i]=w+map[i];
}
w=200;
for(i=p;i<=p+t;++i)
{
if(f[i]<w)w=f[i];
}

//findd(0);
cout<<w;

return 0;
}

请问哪里错了 按理说不该零分啊
program wa;
var
a:array[1..100] of integer;
b:array[-100..1000000] of integer;
l,s,t,m,i,n,min:longint;
begin
readln(l);
readln(s,t,m);
for i:=1 to m do
begin
read(a[i]);
end;
for i:=1 to m do
begin
b[a[i]]:=1;
end;
for i:=t+1 to l do
begin
b[i]:=b[i-s]+b[i];
for n:=s to t do
begin
if ((b[i]+b[i-n])<=(b[i])) and ((i-n)>s) then
b[i]:=b[i]+b[i-n];
end;
end;
min:=32767;
for i:=l to l+t do
if (b[i]<min) and (b[i]<>0) then
min:=b[i];
write(min);
end.

题解：http://www.cnblogs.com/xtx1999/p/4823073.html
有问题请提问，共同进步

Px+(P+1)y=Q x,y是未知数，P是跳跃的距离，P+1也是跳跃的距离，对于任意Q，Q>=P*(P-1), x，y一定存在正整数解，换句话说当两个石子之间的距离大于等于T*(T-1)时，中间有相当大的距离是每个点都可以跳到的，因为没有石子，所以对答案没有贡献，可以取模(%90),这样就很好办了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define inf 1<<30
using namespace std;
int l,s,t,m,f[900000],pos[200],a[900000];
void slove(){
int ans=0;
for(int i=1;i<=m;i++)
if(pos[i]%s==0) ans++;
printf("%d",ans);
}
int main()
{
scanf("%d%d%d%d",&l,&s,&t,&m);
for(int i=1;i<=m;i++)
scanf("%d",&pos[i]);
sort(pos+1,pos+m+1);
if(s==t){
slove();
return 0;
}
for(int i=1;i<=m;i++){
int temp=pos[i]-pos[i-1];
pos[i]=pos[i-1]+temp%90;
}
l=pos[m]+(l-pos[m])%90;
for(int i=1;i<=m;i++)
a[pos[i]]=1;
for(int i=1;i<=l;i++)
f[i]=inf;
f[0]=0;
for(int i=1;i<=l;i++)
for(int j=s;j<=t;j++)
if(i-j>=0)
f[i]=min(f[i-j]+a[i],f[i]);
printf("%d",f[l]);
}

这题……观察到m比较小，我就直接强行检测两个相邻石子距离是否过大但是并没有用滚动数组，交了几次，内存超限或者最多RE50分，强行在滚动数组，调都没调，WA70，后来发现有个式子的优先级搞错了，也没打算改括号，随便写了个较大的数（其实就是当两个石子之间的距离大于这个数时就压缩，所以越大越不影响准确性，只关系到复杂度），第一次直接写t，WA90，再改2*t，居然就AC了233……
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,s,t,a[101],dp[101],b[101],l=0;
int main(){
scanf("%d%d%d%d",&n,&s,&t,&m);
for (int i=1;i<=m;i++) scanf("%d",&a[i]);
if (s==t){
int ans=0;
for (int i=1;i<=m;i++)
if (a[i]%s==0) ans++;
printf("%d\n",ans);
}else{
sort(a+1,a+1+m);
a[0]=0;
int k=t+s;
for (int i=1;i<=m;i++)
if (a[i]-a[i-1]>=k){
int p=a[i]-a[i-1]-t;
for (int j=i;j<=m;j++) a[j]-=p;
b[l]=a[i]-1;
l++;
}
int tt=t+1;
n=a[m];
int u=1,l=0;
for (int i=1;i<=n+t+1;i++){
int p,q=s;
if (i==a[u]) p=1,u++;else p=0;
if (i==b[l]) q=1,l++;
dp[i%tt]=-1;
for (int j=q;j<=min(i,t);j++)
if (dp[(i-j)%tt]!=-1){
if ((dp[i%tt]==-1)||(dp[(i-j)%tt]+p<dp[i%tt])) dp[i%tt]=dp[(i-j)%tt]+p;
}
}
int ans=101;
for (int i=n+1;i<=n+t+1;i++) ans=min(ans,dp[i%tt]);
printf("%d",ans);
}
}

参考了不少题解，终于AC了。也发个题解吧。
题目给人的第一感觉是DP，但注意到L非常大，普通DP无论是空间还是时间都会超的。

空间上：
注意到第i步只会用到i-S到i-T，可以使用滚动数组，大小为T即可
（不需要T+1，但是注意状态转移时要从i-T到i-S，否则会被覆盖，以及恰好踩在石子上时dp[i%T]要先加一）

时间上：
注意到石子个数非常少，石子与石子之间有很大的空白区域。当两点间的距离足够大（应该是>=S*(S-1))时，一定可以到达（S!=T)。
因为走在空白区域，滚动数组中的值会渐趋相同。可以证明，当整个滚动数组里只剩一个值时，只要下一步没有石子，dp值依然会是这个值。因此，我们可以直接跳到下一个石子的位置，此时滚动数组里的值**直接视为**石子前T个位置的dp值，这是没有问题的。
我是用的是记录连续出现的值个数，>T时便可以直接跳到下一个石子。要注意最后一颗石子后要跳到L的处理。

注意：
S==T时上述性质不成立，要特判！
输入的m是无序的，要先排序。

Block Code

#include<iostream>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cstdlib>
using namespace std;

int L;
int S,T,M;
int m[130];
int dp[13];

int ans;

int main()
{
cin>>L>>S>>T>>M;

m[0]=0;
for(int i=1;i<=M;i++) cin>>m[i];
m[M+1]=0;

if(S!=T)
{
sort(m+1,m+1+M,less<int>());
//for(int i=1;i<=M;i++) cout<<m[i]<<" ";
//cout<<endl;
int i=S,p=1;
int Last=101,Count=0;
dp[0]=0;
for(int k=1;k<T;k++) dp[k]=101;
while(i<=L+T)
{
if(i==m[p]) dp[i%T]+=1;
for(int j=T;j>=S;j--) dp[i%T]=min(dp[i%T],dp[(i-j+T)%T]+(i==m[p]));
//cout<<"dp["<<i<<"] = "<<dp[i%T]<<endl;
if(i>=m[p]&&p<=M) p++;
if(dp[i%T]==Last) Count++;
else
{
Last=dp[i%T];
Count=1;
}
i++;
if(Count>T&&i<L)
{
if(p<=M)
{
//p++;
i=m[p];
}
else
{
i=L;
}
Count=0;
//cout<<"Jump to m["<<p<<"]("<<i<<")"<<endl;
//system("pause>>null");
}
}
ans=INT_MAX;
for(int k=L;k<=L+T;k++) ans=min(ans,dp[k%T]);
}
else
{
ans=0;
for(int i=1;i<=M;i++) if(m[i]%S==0) ans++;
}
cout<<ans<<endl;
return 0;
}

用s*t作为路径压缩判断依据，注意s==t时要特判。

#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<iterator>
using namespace std;

vector<int> stones;
map<int,char> is_stone;
map<int,int> memory;
int l,s,t,m,tiaoyue;

int dp(int x)
{
if(x>=l) return 0;
if(x>(*(stones.end()-1))) return 0;
int k=0;
if(memory.count(x)) return memory[x];
for(int i=s;i<=t;i++)
if(is_stone.count(x+i)) {k=1;break;}
int dans=100000;
/*printf("%d : ",k);*/
if(!k)
{
vector<int>::iterator b=upper_bound(stones.begin(),stones.end(),x);
if((*b)-x-s >tiaoyue){
for(int i=(*b)-s;i<=(*b);i++)
{
int a;
a=dp(i);
dans = a<dans ? a : dans;
}

}
else k=1;
}
if(k==1)
{
for(int i=s;i<=t;i++)
{
int a=dp(i+x);
dans= a<dans ? a : dans;
}
}
if(is_stone.count(x)) dans++;
memory.insert(pair<int,int>(x,dans));
/*printf("%d %d\n",x,dans);*/
return dans;
}

int main()
{
scanf("%d%d%d%d",&l,&s,&t,&m);
tiaoyue=s*t;
if(s==t)
{
int ans=0;
for(int i=1;i<=m;i++)
{
int k;
scanf("%d",&k);
if(k%s==0) ans++;
}
printf("%d\n",ans);
return 0;
}
for(int i=0;i<m;i++)
{
int k;
scanf("%d",&k);
stones.push_back(k);
is_stone.insert(pair<int,char>(k,1));
}
sort(stones.begin(),stones.end());
int ans=dp(0);
printf("%d\n",ans);
return 0;
}