记录编号	45409	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2012-10-23 20:46:41	内存使用	1.08 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int l,s,t,m;//l桥长,跳跃距离属于[s,t],m石子数
const int MAX=99999,LSIZE=200011;
int stone[102]={0},f[LSIZE]={0};
void compress(void){//状态压缩
	long i,j,temp;
	for(i=1;i<=m;i++){
		temp=stone[i]-stone[i-1];
		if(temp>3*t){
			temp=((temp/t)-2)*t;//留下冗余
			for(j=i;j<=m;j++) stone[j]-=temp;
		}
	}
	l=stone[m]+10;
}
int dp(){
	int i,j,p=1,temp;
	for(i=1;i<=l+t;i++){
		temp=0;
		if(stone[p]==i) temp=1,p++;//temp为当前位置石头数(1/0)
		for(j=s;j<=t;j++){
			if(i-j>=0&&f[i-j]+temp<f[i]) f[i]=f[i-j]+temp;
		}
	}
	int ans=MAX;
	for(i=l;i<=l+t;i++) if(f[i]<ans) ans=f[i];//要扫描所有跳出的
	return ans;
}
int main(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	cin>>l>>s>>t>>m;
	int i;
	for(i=1;i<=m;i++) cin>>stone[i];
	sort(stone,stone+m+1);//石头位置并未按顺序给出
	compress();
	for(i=1;i<=l+t;i++) f[i]=MAX;//f初始化
	cout<<dp()<<endl;
	return 0;
}