过河
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 737 Accepted Submission(s): 48
Problem Description
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
Input
本题有多组数据。对于每一组数据来说：第一行有一个正整数L（1
<= L <=
109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S
<= T <= 10，1 <= M <=
100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
Output
对于每一组数据，单独输出一行，只包括一个整数，表示青蛙过河最少需要踩到的石子数。(输出的最后没有多余的换行)
Sample Input
10
2 3 5
2 3 5 6 7
Sample Output
2
Source
dp方程很好想 dp[i]=MIN{dp[j]+stone[i]|L-T<=j<=L-S}
由于L很大，无论时间还是空间都是不允许的，我们发现M最多只有100且S，T最大就是10
说明在L很大时石子是很稀疏的，在一大段没有石子的路程中很多的dp[i]都是一样的，我们想到能不能把这段距离给压缩。
当S==T时，跳动的位置都是确定好的我们不能盲目的压缩，只需要统计一下是S倍数位置的石子输出即可。
当S！=T时，如果两个石子间隔大于100，我们将其缩为100，至于为什么是100，其实可以更小这取决与ST大小。
由于这一大段距离没有石子，所以大家的最优解在后面的时候就都一样了。。。前面的几个dp[i]计算出来之后，由于跳动距离的限制，
后面的位置都由这几个位置决定，大家都会选择最优解，所以越往后相似率越高当L很大时就一样了后面的，所以不妨在保持可计算的程度下减小L。
为了防止出错把L也往后延伸了100.
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ql(a) memset(a,0,sizeof(a))
int main()
{
int L,S,T,N,i,j,k=0;
int a[105],b[105],dp[10500],vis[10500];
while(cin>>L>>S>>T>>N){
memset(dp,inf,sizeof(dp));
int sb=0; ql(vis);
if(k!=0) cout<<endl;
for(i=1;i<=N;++i)
{
cin>>b[i];
if(T==S) {
if(b[i]%S==0) sb++;
}
}
if(sb) {cout<<sb;continue;}
sort(b+1,b+1+N);
a[0]=b[0]=0;b[N+1]=L;
for(i=1;i<=N+1;++i){
if(b[i]-b[i-1]>100){
a[i]=a[i-1]+100;
}
else a[i]=a[i-1]+(b[i]-b[i-1]);
if(i!=N+1) vis[a[i]]++;
}
if(a[N+1]!=L) L=a[N+1];
int ans=inf;
for(i=1,dp[0]=0;i<=L+100;++i){
for(j=S;j<=T;++j){
if(i-j>=0)
dp[i]=min(dp[i],dp[i-j]);
}
if(vis[i]>0) dp[i]+=vis[i];
}
for(i=L;i<=L+100;++i) ans=min(ans,dp[i]);
cout<<dp[L];
k++;
}
return 0;
}
using namespace std;
#define inf 0x3f3f3f3f
#define ql(a) memset(a,0,sizeof(a))
int main()
{
int L,S,T,N,i,j,k=0;
int a[105],b[105],dp[10500],vis[10500];
while(cin>>L>>S>>T>>N){
memset(dp,inf,sizeof(dp));
int sb=0; ql(vis);
if(k!=0) cout<<endl;
for(i=1;i<=N;++i)
{
cin>>b[i];
if(T==S) {
if(b[i]%S==0) sb++;
}
}
if(sb) {cout<<sb;continue;}
sort(b+1,b+1+N);
a[0]=b[0]=0;b[N+1]=L;
for(i=1;i<=N+1;++i){
if(b[i]-b[i-1]>100){
a[i]=a[i-1]+100;
}
else a[i]=a[i-1]+(b[i]-b[i-1]);
if(i!=N+1) vis[a[i]]++;
}
if(a[N+1]!=L) L=a[N+1];
int ans=inf;
for(i=1,dp[0]=0;i<=L+100;++i){
for(j=S;j<=T;++j){
if(i-j>=0)
dp[i]=min(dp[i],dp[i-j]);
}
if(vis[i]>0) dp[i]+=vis[i];
}
for(i=L;i<=L+100;++i) ans=min(ans,dp[i]);
cout<<dp[L];
k++;
}
return 0;
}