记录编号	334019	评测结果	AAAAAAAAAA
题目名称	111.[NOIP 2005]过河	最终得分	100
用户昵称	dududu	是否通过	通过
代码语言	C++	运行时间	0.311 s
提交时间	2016-10-31 17:41:05	内存使用	57.54 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define KN 5000010
#define LL long long
int pos[KN];
int L,S,T,M,mod;
int v[KN];
int f[KN];

void special_sol(){
	
	int cnt=0;
	for(int i=1;i<=M;i++){
		if(!(pos[i]%S)) cnt++;
	}
	printf("%d",cnt);
}

void sol(){
	
	memset(f,0x3f,sizeof f);
	
	f[0]=0;

	int pre_pos;
	for(int i=1;i<=L;i++){
		for(int j=S;j<=T;j++){
			pre_pos=i-j;
			if(pre_pos<0) break;
			f[i]=min(f[i],f[pre_pos]+v[i]);	
		}
	}
	
	printf("%d",f[L]);
}

void init(){
	
	scanf("%d%d%d%d",&L,&S,&T,&M);
	
	for(int i=1;i<=M;i++) scanf("%d",&pos[i]);
	sort(pos+1,pos+M+1);
	
	if(S==T){
		special_sol();
		return;
	}
	
	mod=90;
	
	int tmp;
	for(int i=1;i<=M;i++){
		tmp=pos[i]-pos[i-1];
		pos[i]=pos[i-1]+tmp%mod;
	}
	L=pos[M]+(L-pos[M])%mod;
	
	for(int i=1;i<=M;i++) v[pos[i]]=1;
	
	sol();
}



int main(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	init();
	return 0;
}