原题
先想一下思路，由于是区间跳跃，不能用贪心，那么f[i]表示跳到i时最少踩到的石子数，i只能由i-t~i-s转移过来，所以选择其中的最小值跳，保证f[i]最小。
但是l太大了，1e9，但是m和t很小，就是1e9中有很多没有用的空间，我们求终点的值，所以中间废掉的空间可以省略，缩点之后用还能用单调队列优化一下。
#include<iostream> #include<cstdio> #include<cstring> #include<iomanip> #include<algorithm> using namespace std; int r,s,t,m,a[10001],b[101],maxx,f[10001],cha[102],q[100001],head=1,tail=0; int cmp(int x,int y) { return x<y; } int main() { cin>>r>>s>>t>>m; for(int i=1;i<=m;++i) cin>>a[i]; if(s==t) { int ans=0; for(int i=1;i<=m;++i) if(a[i]%s==0) ans++; cout<<ans; return 0; } sort(a+1,a+m+1,cmp); for(int i=1;i<=m;++i) { cha[i]=a[i]-a[i-1]; if(cha[i]>90) cha[i]=90; }cha[m+1]=min(r-a[m],100); memset(a,0,sizeof(a));int l=0; for(int i=1;i<=m;++i) { l+=cha[i]; a[l]=1; } l+=cha[m+1]; for(int i=0;i<=l+10;++i) f[i]=99999; f[0]=0;int cnt=1; for(int i=1;i<l+10;++i) { if(q[head]<i-t&&head<=tail) head++; while(f[i-s]<=f[q[tail]]&&head<=tail) tail--; if(i-s>=0)q[++tail]=i-s; f[i]=f[q[head]]+a[i]; if(i-s<0) f[i]=999999; }int ans=999999; for(int i=l;i<l+10;++i) if(f[i]<ans) ans=f[i]; cout<<ans; return 0; }
