1087.过河解题报告(没写完)

设f[n]表示青蛙到达n位置最少需要踩到的石子数。
rock[n]=1(n位置有石子)，0(n位置无石子)
f[n]=min{f[n-i]+rock[n]}(s<=i<=t)
这个方程时间复杂度是O(n)，在本题的1e9极限数据是无法出解的。
优化方法：压缩法
结论：px+(p+1)y=Q
若采用跳跃距离p，p+1时可以跳至任何位置Q，则在Q>=p(p+1)时是一定有解的。
证明：
由于p和p+1互质，因此该不定方程有解，设解为x=x0+(p+1)t,y=y0+pt
那么使得0<=x<=p,则当Q>p(p-1)-1时，有(p+1)y=Q-px>p(p-1)-1-pp=-(p+1)
故y>-1,也就是y>=0
由于题目给出一个区间，1<=s<=t<=10,于是当相邻两个石子间距离不超过89=72时，后面的距离都可到达，这样就把它们的距离缩小为72100，动态规划算法就完全可以承受了。但在s=t的时候时不能用的，这种情况下，统计出坐标是s倍数的就可以了。