记录编号	68153	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]过河	最终得分	100
用户昵称	老师好~~~	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-08-17 11:53:26	内存使用	0.47 MiB

/*路径压缩DP by raywzy*/
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("river.in");
ofstream fout("river.out");
int L,S,T,M;
int a[102];
int b[20000];
int f[20000];
int maxn=99999999;
int counter=0;
int main()
{
	fin>>L>>S>>T>>M;
	int i,j,p;
	for(i=1;i<=M;i++)
		fin>>a[i];
	sort(a+1,a+M+1);//数据无序
	if(S==T)
	{
		for(i=1;i<=M;i++)
			if(a[i]%S==0)
				counter++;
		fout<<counter<<endl;
		return 0;
	}
	for(i=0;i<=M;i++)
	{
		if(a[i+1]-a[i]>S*T)
		{
			p=a[i+1]-a[i]-S*T;
			for(j=i+1;j<=M;j++)
				a[j]-=p;
		}
	}//路径压缩
	for(i=1;i<=19999;i++)
		b[i]=0;
	for(i=1;i<=M;i++)
		b[a[i]]=1;//将有石子的点标记
	for(i=0;i<=19999;i++)
		f[i]=99999999;
	for(i=S;i<=T;i++)
	{
		if(b[i]==1)
			f[i]=1;
		else
			f[i]=0;
	}//动规初始化
	for(i=T+1;i<=a[M]+T;i++)
		for(j=S;j<=T;j++)
		{
			if(f[i]>f[i-j]+b[i])
				f[i]=f[i-j]+b[i];
		}//动规实现
	for(i=a[M];i<=a[M]+T;i++)
	{
		if(f[i]<maxn)
			maxn=f[i];
	}
	fout<<maxn<<endl;
	return 0;
}