#include <stdio.h> #include <stdlib.h> #include <string.h> #define maxn 10010 #define inf 1000000000 int f[maxn]; int a[110]; int cmp(const void * a, const void * b) { return ((*(int*)a) - (*(int*)b)); } int main() { int L,S,T,M; scanf("%d%d%d%d",&L,&S,&T,&M); memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); for(int i = 1;i <= M; i++)scanf("%d",&a[i]); if(S==T) { int ans = 0; for(int i = 1;i <= M; i++) { ans += !(a[i]%S); } printf("%d\n",ans); return 0; } qsort(a+1,M,sizeof(int),cmp); int p = 0; if(a[1]>100) f[p=100]=1; else f[p=a[1]]=1; for(int i = 2;i <= M; i++) { if(a[i]-a[i-1]>100)f[p=p+100]=1; else f[p=p+a[i]-a[i-1]]=1; } if(L-a[M]>100)p=p+100; else p=p+L-a[M]; for(int i = 1;i <= p; i++) { int b = inf; for(int j = S;j<=T;j++) { if(i-j>=0)b=b>f[i-j]?f[i-j]:b; } if(b!=inf)f[i]+=b; else f[i]=inf; } int ans = inf; for(int i = p-T;i<=p;i++)ans = ans>f[i]?f[i]:ans; printf("%d\n",ans); return 0; } /************************************************************** Problem: 2257 User: admin Language: C Result: Accepted Time:49 ms Memory:1184 kb ****************************************************************/