强题啊！这么多题解

为什么我死于第6点

有同样错过但改过来的人提提吗

正确是1,我输出0

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

barty好像是直接copy王建德教授的原程序!

忘记排序,存取非法,WA N次.....

太恼火了，s=t的时候还不能直接就用dp，而是直接模拟。

我真的是~~~~~搞不懂为什么~~~因为不耐心，没等验证码刷出来，就点了提交，结果~~提交成功了，而且……AC了~~~~~~~ 汗一个~~终于明白那个地方为什么是t-1而不是t了……哈哈~~~~~~~~因为t 和 0 能够到达的是一个地方

又要排序......

为什么要大于100压成100,20不行么?

第一次写题解哈~~~

去年就栽在这里了，这题确实有些陷阱。

DP是肯定的，关于如何压缩，个人想到的方法就是先对数据排个序。

往回搜的时候，每碰到一个石头就读出下一个在哪里（最开始的那个很好读吧？），后面就可以直接用这次记住的东西。滚动数组即使非常小也同样有高效率，因为知道下一个石头在哪里，当你填满一次数组后就可以直接把当前处理的位置向桥头移动数组长度的整数倍位（当然是不能移到石头前面去的，整数倍时为了保持相对位置）。

至于S=T，确实是用%就对了,而且意思好懂，但是没想通为何DP就不对了，不知哪位大牛说明下？

首先提交了N次（N>=10）次总是80分，后来发现S=T的时候不能剪去空白，改正后，终于AC了

大于110按110算是怎么来的呀？谁能给我一个数学证明？

贪心的确是个很好的策略{在考试时}

单纯把大间距减小到100 or s*t均是不对的

关于离散化的补充：其实，在离散化的过程中“大于一定范围的点”是有规律可循的。除过s=t例外，显然当t=s+1 时“大于一定范围的点”最大。设a表示题目中两点范围，b为离散化后的点； 对于这点，可假设全部使用全部用t步，在通过可递减范围确定这个离散化的点。（有点类似小学时的鸡兔同笼）经计算可得到这个公式，当最大步数为t时，有—— b=(2s-t-1)*t+1.（不过，当b

模拟一下dp过程 发现其中冗杂多余重复的步骤 然后找到预处理的方法 最后就直接 dp处理以后的数据

DP 注意排序石子距离 注意s=t

看起来是个简单的动态规划，但是数据十分大，所以直接动态规划时不行的。注意到石头非常稀疏，所以在距离大于一定范围的点总是可以到达的，经试验这个值取90即可。所以对于距离大于90的两块石头把他们的距离设为90，然后用原来的规划方程来动态规划。不过在S=T的情况下要注意一下，不能用这种压缩距离的方法做，而要直接看能否走到。

压缩路径...

若两棵石头的间隔大于100，则令它们的距离为100，再DP

....................................

So easy 的方法，05.11.19上午我为什么没敢试试呢？？？？？？？？？

郁闷ing.................

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN=1E6;
const int MAXM=105;
const int MOD=100;

int l,s,t,m,ans=0x7fffffff;
int M[MAXM],F[MAXN];
bool stone[MAXN];

int main()
{
memset(F,0x7f,sizeof(F));
F[0]=0;
scanf("%d",&l);
scanf("%d %d %d",&s,&t,&m);
for(int i=1;i<=m;i++)
scanf("%d",&M[i]);
sort(M+1,M+m+1);
if(s==t)
{
ans=0;
for(int i=1;i<=m;i++)
if(M[i]%s==0)
ans++;
cout<<ans<<endl;
return 0;
}
for(int i=1;i<=m;i++)
{
int x=M[i]-M[i-1];
M[i]=M[i-1]+x%MOD;
stone[M[i]]=1;
}
for(int i=1;i<=M[m]+t;i++)
{
for(int j=s;j<=t;j++)
if(i-j>=0)
F[i]=min(F[i],F[i-j]);
if(stone[i]) F[i]++;
}
for(int i=M[m];i<=M[m]+t;i++)
ans=min(ans,F[i]);
cout<<ans<<endl;
return 0;
}

经典状态压缩DP
F[i]=min{F[j]}+1 j∈[i-S,i-T]
从数据范围109来看，直接DP不是TLE就是MLE，所以不能硬怼
桥长109，石子只有100个，最远跳10格，就算石子在怎么平均分配，两个石子之间都有107的长度是空着的，这段距离任凭青蛙怎么跳，最少踩到的石子数都不会变。
那么问题来了，石子之间距离多少时可以进行压缩？
我们先画个数轴
![]https://images2017.cnblogs.com/blog/938173/201708/938173-20170814153816975-1241276689.png)
为了更好说明：这里的0不是指原点，表示青蛙当前位置
假设0前面就是一块石子，从0开始后的点都是空地，S~T之间的nx表示青蛙能到达的位置，当红色区域间隔≤0时，后面将不再有青蛙到不了的地方，因此后面的区域能够到任意位置
证明开始：
设T-S=Δx
nS-(n-1)T<=0
nS-nT+T<=0
T<=n(T-S)
T<=n*Δx
因此：
n=ceil(T/Δx)
间隔的距离为n*T
Δx=1时，n=T最大
因此间隔距离最大为T2，T=10最大，因此最大间隔距离为T2=100
为什么不是n*S呢？青蛙跳过0前的石子后，不一定就到0上，也可能到了0~T-1的位置上，0～T-1包括0～S这一段，这些点也要包括，因此是n*T。
不过要注意：Δx=0 时，也就是S=T时需要特判
这个时候，直接判断石子位置，M[i]%S==0，即可
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN=1E6;
const int MAXM=105;
const int MOD=100;

int l,s,t,m,ans=0x7fffffff;
int M[MAXM],F[MAXN];
bool stone[MAXN];

int main()
{
memset(F,0x7f,sizeof(F));
F[0]=0;
scanf("%d",&l);
scanf("%d %d %d",&s,&t,&m);
for(int i=1;i<=m;i++)
scanf("%d",&M[i]);
sort(M+1,M+m+1);
if(s==t)
{
ans=0;
for(int i=1;i<=m;i++)
if(M[i]%s==0)
ans++;
cout<<ans<<endl;
return 0;
}
for(int i=1;i<=m;i++)
{
int x=M[i]-M[i-1];
M[i]=M[i-1]+x%MOD;
stone[M[i]]=1;
}
for(int i=1;i<=M[m]+t;i++)
{
for(int j=s;j<=t;j++)
if(i-j>=0)
F[i]=min(F[i],F[i-j]);
if(stone[i]) F[i]++;
}
for(int i=M[m];i<=M[m]+t;i++)
ans=min(ans,F[i]);
cout<<ans<<endl;
return 0;
}