题解

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int L,S,T,M;
long long pos[5000000];
long long f[5000000];
long long a[5000000];
void calc(){
long long ANS=0;
for(long long i=1;i<=M;i++){
if(pos[i]%S==0)
ANS++;
}
cout<<ANS;
return ;
}
int main(){

scanf("%d%d%d%d",&L,&S,&T,&M);
for(long long i=1;i<=M;i++) scanf("%d",&pos[i]);
sort(pos+1,pos+M+1);//石头位置排序

if(S==T){
    calc();
    return 0;
}

for(long long i=1;i<=M;i++){
    long long delta=pos[i]-pos[i-1];
    if(delta>90){
        pos[i]=pos[i-1]+delta%90;
    }
}

L=pos[M]+(L-pos[M])%90;

for(long long i=1;i<=M;i++){
    a[pos[i]]=1;
}

for(long long i=1;i<=L;i++) f[i]=inf;
f[0]=0;

for(long long i=1;i<=L;i++){
    for(long long j=S;j<=T;j++){
        long long pos1=i-j;
        if(pos1<0) break;
        f[i]=min(f[i],f[pos1]+a[i]);
    }
}
cout<<f[L];

return 0;

}