[vijos1002]-[NOIP2005]过河

题目（vijos）
这题先看题：不用说，简直水的dp。
然后再看数据范围......
呵呵。
 
 
那么这题该怎么去做呢？
dp方程其实很好推，设b数组是用来存第i个点是否有石子，
所以方程为:dp[i]=min(dp[i],dp[i-j]+b[i])，其中s<=j<=t。
但是这个L<=10^9……
不用急，看看m的范围：m<=100。
什么意思呢？就是说在这段很长的桥中，只有100个点有石子。
这就表明：有很多空点，很多的空点我们是不用考虑的。
于是可以压缩状态。
我们再发现，t最多只有10，所以这里就是个比较玄学的方法了：每两个石子之间的长度取模100或者更多，变为新的距离。这样，很多的空点就可以去除掉了。
为什么可以这样？
可以感受一下：两者之间的有效距离<=s*t，具体证明有点复杂，暂时不写。
然后就做完啦~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int l,s,t,m;
int a[105];
int dp[2000005];
int b[2000005];
int ans=0x3f3f3f3f;
int main()
{
	memset(dp,63,sizeof dp);
	dp[0]=0;
	scanf("%d%d%d%d",&l,&s,&t,&m);
	for (int i=1;i<=m;++i)
		scanf("%d",&a[i]);
	sort(a+1,a+m+1);
	if (s==t)
	{
		int tot=0;
		for (int i=1;i<=m;++i)
			if (a[i]%s==0) ++tot;
		printf("%d",tot);
		return 0;
	}
	for (int i=1;i<=m;++i)
	{
		int dis=a[i]-a[i-1];
		a[i]=a[i-1]+dis%100;
	}
	l=(l-a[m])%100+a[m];
	for (int i=1;i<=m;++i)
		b[a[i]]=1;
	for (int i=s;i<=l+t;++i)
	{
		for (int j=s;j<=t;++j)
		{
			if (i>=j)
			dp[i]=min(dp[i],dp[i-j]+b[i]);
		}
	}
	for (int i=l;i<=l+t;++i)
		ans=min(ans,dp[i]);
	printf("%d",ans);
	return 0;
}