题意:在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧.在桥上(M)个石子，青蛙很讨厌踩在这些石子上.由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：(0,1,…,N)（其中(N)是桥的长度）.坐标为(0)的点表示桥的起点，坐标为(L)的点表示桥的终点.青蛙从桥的起点开始，不停的向终点方向跳跃.一次跳跃的距离是(L)到(R)之间的任意正整数（包括(L,R)）.当青蛙跳到或跳过坐标为(N)的点时，就算青蛙已经跳出了独木桥.题目给出独木桥的长度(N)，青蛙跳跃的距离范围(L,R)，桥上石子的位置.你的任务是确定青蛙要想过河，最少需要踩到的石子数.(N<=1e9.1<=L<=R<=10,M<=100)
分析:不考虑N如此之大的话,其实本题是很容易做的,设(f[i])表示青蛙跳到i点时最少需要踩到的石子数,则(f[i]=min_{j=l}^r(f[i],f[i-j])+bj[i]),其中(bj[i])表示i点是否是石子.
但是因为(N<=1e9),我们连数组都开不了.所以要考虑优化,一般这种情况很容易想到是要离散化,但是本题并不能普通的离散化.然后题解告诉我,每次走(p)步或者(p+1)步，(p*(p+1))之后的地方均能够到达.联系本题,(R)最大为10,所以大于(9*10=90)的地方均能够到达,所以只要这中间没有石子,我们就可以直接把这一段给忽略掉.
具体来说,对于没两颗相邻的石子,如果它们之间的距离大于90,那么就直接赋值为90就行了.这样我们就能够像上面那样设状态和转移了.
但是还有一种情况一定要特判:(l=r),对于这种每次都是走l步的情况,我们直接判断,如果石子所在位置能被l整除,这颗石子就会被踩到.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=10005;
int a[N],dis[N],bj[N],f[N];
int main(){
int n=read(),l=read(),r=read(),m=read();
for(int i=1;i<=m;++i)a[i]=read();
if(l==r){//特判
int ans=0;
for(int i=1;i<=m;++i)if(a[i]%l==0)++ans;
printf("%d
",ans);return 0;
}
sort(a+1,a+m+1);//把石子按照位置从小到大排序
dis[m+1]=min(n-a[m],100);
//最后一段因为青蛙可以跳过n,所以90+max{r}=100都是有可能的跳到的
n=0;
for(int i=1;i<=m;++i){
dis[i]=min(a[i]-a[i-1],90);
n+=dis[i];bj[n]=1;
}
n+=dis[m+1];
memset(f,0x3f,sizeof(f));f[0]=0;
for(int i=1;i<=n+9;++i){
for(int j=l;j<=r;++j){
if(i-j>=0)f[i]=min(f[i],f[i-j])+bj[i];
}
}
int ans=1e9;
for(int i=n;i<=n+9;++i)ans=min(ans,f[i]);
printf("%d
",ans);
return 0;
}