记录编号	458480	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	FFF团	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-10-11 14:41:42	内存使用	0.37 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int stone[105],f[10105];
bool rock[10105];
int L,S,T,M,ans=101;
int main(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	
	scanf("%d",&L);
	scanf("%d%d%d",&S,&T,&M);
	int D=T*(T-1),x=0;
	for(int i=1;i<=M;i++)scanf("%d",&stone[i]);	
	if(S==T){
		ans=0;
		for(int i=1;i<=M;i++)
		if(stone[i]%S==0)ans++;
		printf("%d",ans);
		return 0;
	}
	stone[M+1]=L;
	sort(stone+1,stone+M+1);
	for(int i=1;i<=M+1;i++){
		if(stone[i]-stone[i-1]>D)
		x+=stone[i]-stone[i-1]-D;
		rock[stone[i]-x]=1;
	}
	L-=x;
	rock[L]=0;
	memset(f,0x7f,sizeof(f));
	f[0]=0;
	for(int i=S;i<=L+T;i++)
	for(int k=S;k<=T;k++)
	if(i-k>=S||i-k==0){
		if(!rock[i])f[i]=min(f[i-k],f[i]);
		else f[i]=min(f[i-k],f[i])+1;
	}
	for(int i=L;i<L+T;i++)
	ans=min(f[i],ans);
	printf("%d",ans);
	return 0; 
}