记录编号	467920	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-10-31 15:31:44	内存使用	7.94 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
/*
	不压缩，30分算法； 
	压缩路径，类比小奇挖矿这题当两个点距离超过90
	(其实s，t最小公倍数就行了)这个是错的，得是90，90不会超过任何一组s，t的最小公倍数； 
	就把两者距离压缩；%90；
	然后最坏情况，90*100=9000
	这里我们采用一种非常非常暴力的方法；
	直接开1e5避开很多细节问题；
	比如越界之类的。 
	扫结果也非常暴力地扫，从最大的位置往后多扫90； 
*/ 
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=150;
int len,s,t,n;
int p[maxn];
int f[1000050];
int cnt[1000050];
int main(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	len=read();
	s=read();t=read();n=read();
	int lim=90;
	for(int i=1;i<=n;i++){
		p[i]=read();
	}
	p[n+1]=len;
	sort(p+1,p+n+2);
	if(len>10000)
		for(int i=0;i<=n;i++){
			int dis=p[i+1]-p[i];
			if(dis>=lim)p[i+1]=p[i]+(dis%lim);
		}
	for(int i=1;i<=n;i++)cnt[p[i]]++;
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0]=0;
	for(int i=0;i<=(int)1e5;i++){
		if(f[i]==inf)continue;
		for(int j=i+s;j<=i+t;j++){
			int pos=j;
			if(cnt[pos])f[pos]=min(f[pos],f[i]+cnt[pos]);
			else f[pos]=min(f[pos],f[i]);
		}
	}
	int ans=inf;
	ans=min(ans,f[p[n+1]]);
	for(int i=p[n+1];i<=p[n+1]+90;i++){
		ans=min(ans,f[i]);
	}
	cout<<ans<<endl;
	return 0;
}