记录编号	238642	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-03-19 11:39:50	内存使用	0.00 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
namespace cat{
	int l,s,t,m;
	int a[102],f[200010];
	inline int cat_min(const int a,const int b){
		return a<b? a:b;
	}
	void cat_(){
		sort(a+1,a+m+1);
		int temp;
		for(int i=1;i<=m;i++){
			temp=a[i]-a[i-1];
			if(temp>10*t){
				temp=((temp/t)-9)*t;
				for(int j=i;j<=m;j++) a[j]-=temp;
			}
		}
		l=a[m];
	}
	int doo(){
		freopen("river.in","r",stdin);
		freopen("river.out","w",stdout);
		scanf("%d%d%d%d",&l,&s,&t,&m);
		for(int i=1;i<=m;i++) scanf("%d",&a[i]);
		cat_();
		for(int i=1;i<=l+t;i++) f[i]=0x7fff;
		int p=1,temp;
		for(int i=1;i<=l+t;i++){
			if(a[p]==i) {
				p++;
				for(int j=s;j<=t && j <=i;j++){
					f[i]=cat_min(f[i],f[i-j]+1);
				}
			}
			else for(int j=s;j<=t && j<=i;j++){
				f[i]=cat_min(f[i],f[i-j]);
			}
		}
		int ans=0x7fff;
		for(int i=l;i<=l+t;i++) if(f[i]<ans) ans=f[i];
		printf("%d\n",ans);
		return 0;
	}
}
int asd = cat::doo();
int main(){;}