$30pts$
状态和转移都比较好想：设$f[i]$表示跳到$i$位置，踩到的最小石子数。转移方程也很明了，为$f[i]$=$min${$f[i-j]$)，,这个位置有石子时答案再加1，$s<=j<=t$。
但是出了几次小坑 ：首先答案不一定是$f[l]$，因为可能跳过去，但也算到达彼岸了。其次我用的$stone$数组不再代表石子个数，而是下标，所以开到$10000$。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 5 using namespace std; 6 7 int l,s,t,m,ans=20000; 8 int f[20000],stone[20000]; 9 10 int main() 11 { 12 scanf("%d%d%d%d",&l,&s,&t,&m); 13 for(int i=1;i<=m;i++) 14 { 15 int qwq=0; 16 scanf("%d",&qwq); 17 stone[qwq]=1; 18 } 19 memset(f,127,sizeof(f)); 20 f[0]=0; 21 for(int i=0;i<=l;i++) 22 { 23 for(int j=s;j<=t;j++) 24 { 25 if(i-j<0) break; 26 f[i]=min(f[i-j],f[i]); 27 } 28 if(stone[i]) f[i]++; 29 } 30 for(int i=0;i<=t;i++) ans=min(ans,f[l-i]+stone[l]); 31 printf("%d",ans); 32 return 0; 33 }
$100pts$
下标太大了呀...达到了丧心病狂的$1e9$。考虑优化，转移貌似没得搞，考虑状态优化。其实注意到这个条件我们首先就应该想到离散化。因为虽然长度很大，但石子个数却很小。也就是说，两个石子间可能会有很长的空隙。
有两个压缩方法：膜2520和膜72。（一步青蛙最多跳10个单位）2520是1,2,3,4,5,6,7,8,9,10的最小公倍数，因此从一个点出发，无论青蛙能跳多少距离，它一定能到2520。当两个石子间的距离大于2520，我们对其取膜。因为当距离大于2520时，我们一定可以连续跳某次，不经过任何石子。这样我们就成功地进行了离散化。
同上，最后我们还要枚举跳过（一声）的情况。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define maxn 1000000 5 6 using namespace std; 7 8 int l,s,t,m,ans=2520; 9 int stone[maxn],d[maxn],flag[maxn],f[maxn]; 10 11 int main() 12 { 13 scanf("%d",&l); 14 scanf("%d%d%d",&s,&t,&m); 15 for(int i=1;i<=m;i++) scanf("%d",&stone[i]); 16 sort(stone+1,stone+1+m); 17 for(int i=1;i<=m;i++) d[i]=(stone[i]-stone[i-1])%2520; 18 for(int i=1;i<=m;i++) 19 { 20 stone[i]=stone[i-1]+d[i]; 21 flag[stone[i]]=1; 22 } 23 memset(f,127,sizeof(f)); 24 f[0]=0; 25 for(int i=1;i<=stone[m]+t;i++) 26 { 27 for(int j=s;j<=t;j++) 28 { 29 if(i-j<0) break; 30 f[i]=min(f[i-j],f[i]); 31 } 32 if(flag[i]) f[i]++; 33 } 34 for(int i=0;i<=t;i++) ans=min(ans,f[i+stone[m]]); 35 printf("%d",ans); 36 return 0; 37 }