记录编号	452461	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	Menamovic	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-09-19 17:11:06	内存使用	2.61 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int L;
int s,t,m;
int a[1010];
int f[300010],stone[300010]={0};
int k;

int min(int a,int b){return a<b?a:b;}

int main()
{
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
//	ios::sync_with_stdio(false);
	cin>>L;
	cin>>s>>t>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++)
	{
		if(a[i]-a[i-1]>2520)//2520为1~10的最小公倍数
		{
			k+=(a[i]-a[i-1])-(a[i]-a[i-1])%2520;
		}
		stone[a[i]-k]=1;
	}//路径压缩
	memset(f,0x7f,sizeof(f));
	f[0]=0;
	int z=252000;
	for(int i=1;i<=z;i++)
	{
		for(int j=s;j<=t;j++)
		{
			if(i>=j) f[i]=min(f[i],f[i-j]+stone[i]);
		}
	}
	cout<<f[z];
	return 0;
}