Description
给定一条数轴，起点为0，数轴的某些整数点上有石子。每次可以移动的区间为[S,T]。求当到达或超过L时，最少踩到的石子数。
Input
输入的第一行有一个正整数L(1 <= L <= 109)。
第二行有三个正整数S,T,M，M表示桥上石子的个数，其中1 <= S <= T <= 10,1 <= M <= 100。
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的0和L处没有石子)。所有相邻的整数之间用一个空格隔开。
Output
输出只包括一个整数，表示最少踩到的石子数。
Sample Input
10
2 3 5
2 3 5 6 7
Sample Output
2
Solution
首先列出dp方程，f[i]表示到达i时最少踩到的石子数，则f[i]=min(f[i-k])(S<=k<=T)。
然后发现数据范围是109，所以需要状压一下。
经过思考可以发现，如果在k+S×T和k+S×T+x(k>=0,x>0)处有石子，则若存在一种方案可以越过k+S×T，那么也能越过k+S×T+x。
具体证明时把S×T看成T个S相加，易证能到达k+S×T，也能到达k+S×T+x。
所以只需将距离超过S×T的石子距离缩到S×T就可以了。
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 101
#define L 20001
using namespace std;
int a[M],f[L],l,m,s,t;
bool sto[L];
inline void init(){
scanf("%d%d%d%d",&l,&s,&t,&m);
for(int i=;i<=m;i++)
scanf("%d",&a[i]);
sort(a+,a++m);
if(s==t){
for(int i=;i<=m;i++)
if(!(a[i]%s)&&a[i]<=l)
f[]++;
printf("%d\n",f[]);
return;
}
for(int i=,d;i<=m;i++){
if(a[i]-a[i-]>s*t){
d=a[i]-a[i-]-s*t;
for(int j=i;j<=m;j++)
a[j]-=d;
}
sto[a[i]]=true;
}
if(l-a[m]>s*t) l=a[m]+s*t;
fill(f+,f++l,M);
for(int i=s;i<=l;i++){
f[i]=f[i-s];
for(int j=min(t,i);j>=s;j--)
f[i]=min(f[i],f[i-j]);
f[i]+=sto[i];
}
printf("%d\n",f[l]);
}
int main(){
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}