记录编号	32348	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.948 s
提交时间	2011-11-06 16:06:35	内存使用	0.95 MiB

#include <cstdio>
#include <cstdlib>
using namespace std;

void swap(int &x,int &y)
{
	int temp;
	temp=x;
	x=y;
	y=temp;
}

void qqsort(int* num,int l,int r)
{
	int ll,rr,temp;
	ll=l;
	rr=r;
	temp=num[rand()%(r-l+1)+l];
	while (ll<=rr)
	{
		while (num[ll]<temp)
			ll++;
		while (temp<num[rr])
			rr--;
		if (ll<=rr)
		{
			swap(num[ll],num[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(num,l,rr);
	if (ll<r)
		qqsort(num,ll,r);
}

int main(void)
{
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	int i,j,n,dis,minlen,maxlen,minnum,num=1,pos[200]={0},f[200000]={0};
	scanf("%d\n%d %d %d\n",&dis,&minlen,&maxlen,&n);
	for (i=1;i<=n;i++)
		scanf("%d",&pos[i]);
	qqsort(pos,1,n);
	for (i=1;i<=n;i++)
		while (pos[i]-pos[i-1]>200*maxlen)
		{
			for (j=i;j<=n;j++)
				pos[j]-=100*maxlen;
			dis-=100*maxlen;
		}
	while (dis-pos[n]>200*maxlen)
		dis-=100*maxlen;
	for (i=1;i<minlen;i++)
		f[i]=2000000000;
	for (i=minlen;i<=dis+100*maxlen;i++)
	{
		minnum=f[i-minlen];
		for (j=minlen+1;j<=maxlen;j++)
		{
			if (i-j<0)
				break;
			if (f[i-j]<minnum)
				minnum=f[i-j];
		}
		while (i>pos[num])
			num++;
		if (i==pos[num])
		{
			num++;
			minnum++;
		}
		f[i]=minnum;
	}
	minnum=f[dis+100*maxlen];
	for (i=dis+100*maxlen-1;i>=dis;i--)
		if (f[i]<minnum)
			minnum=f[i];
	printf("%d\n",minnum);
	fclose(stdin);
	fclose(stdout);
	return(0);
}