题目

青蛙从0开始，不停的向终点跳跃。一次跳跃的距离是$S$到$T$之间的任意正整数（包括 $S,T$）。当青蛙跳到或跳过坐标为 $L$ 的点时，就算青蛙已经跳出了独木桥。问最少要踩多少石子过去。

---

分析

动态规划，注意路径压缩，状态转移方程：
f [ i ] = min ⁡ { f [ i − j ] } + h a v e − s t o n e [ i ] f[i]=\min\{f[i-j]\}+have-stone[i] f[i]=min{f[i−j]}+have−stone[i]

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
int l,s,t,n,a[101],f[252011],ans; bool stone[252011];
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int main(){in(); s=in(); t=in(); ans=n=in();for (int i=1;i<=n;i++) a[i]=in();stable_sort(a+1,a+1+n); int ls=0;for (int i=1;i<=n;i++){int lt=ls; ls=a[i];a[i]=a[i-1]+(a[i]-lt)%2520;//离散，因为最多走十步，所以肯定是1~10的最小公倍数stone[a[i]]=1;//标记有石头}l=a[n];for (int i=1;i<=l+t;i++) f[i]=n;//n个石头都走for (int i=1;i<=l+t;i++)for (int j=s;j<=t;j++){if (i-j>=0) f[i]=(f[i]<f[i-j])?f[i]:f[i-j];//怎样少走石头f[i]+=stone[i];//如果有石头要走一块}for (int i=l;i<l+t;i++) ans=(ans<f[i])?ans:f[i];return !printf("%d",ans);
}