由于L的范围到了109,用普通dp做肯定是不成了;
可以观察到M的数量很小,dp在转移的过程中有大量的无用转移;
可以想到压缩范围,问题是如何压缩,观察若S=9,T=10时,能到达的点,9,10,18,19,20,27,28,29,30,36,37,38,39,40....80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120...
观察到了一定限度以后,可以跳到任意一个点;
所以可以根据这个压缩,压缩到100就可以了;
有一个地方需要注意,若S=T,要特判,不能压缩;
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
using namespace std;
const int maxn=,maxm=;
int L,S,T,M,N;
int a[maxn];
int vis[maxm],f[maxm];
void init(){
scanf("%d%d%d%d",&L,&S,&T,&M);
for(int i=;i<=M;i++)scanf("%d",&a[i]);
sort(a+,a+M+);
}
void work(){
int last=;
for(int i=;i<=M;i++){
if(a[i]-a[i-]>){vis[last+=]=;}
else {vis[last+=a[i]-a[i-]]=;}
}
if(S==T){
int sum=;
for(int i=;i<=M;i++)if(a[i]%S==)sum++;
cout<<sum<<endl;
return;
}
N=last;
memset(f,,sizeof(f));
f[]=;
for(int i=;i<=N+;i++){
for(int j=S;j<=T;j++)f[i+j]=min(f[i+j],f[i]+vis[i+j]);
}
int minn=(<<);
for(int i=N+;i<=N+;i++)minn=min(minn,f[i]);
cout<<minn<<endl;
}
int main(){
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
init();
work();
}