题目描述Description
,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。
输入描述Input Description
个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。
输出描述Output Description
输出只包括一个整数,表示青蛙过河最少需要踩到的石子数。
样例输入Sample Input
1067
样例输出Sample Output
2
数据范围及提示Data Size & Hint
数据规模
109。
方程显然:
f[i] = min { f[i – x] } + stone[i]; x∈[S, T]ans = min {f[j]}; j∈[L, L+T-1]
既然数据这么大,显然要离散化
一开始离散的t,但是怎么也过不了 不知是不是杨志灿老师的课件有误。codevs上也有说t的,不知为什么;
引用codevs上最小公倍数做法的解释:
只要求出1–10里面任意两个数的最小公倍数,然后取最大的,,可以证明当两石块之间的距离大于它的时候,那么大于它的部分的每一个点都可以通过这两个数的某一种组合跳到,所以当两个石块间的距离大于这个最小公倍数,那么就把它们的距离缩小到这个最小公倍数.路径压缩后,就可以DP求出最小踩石子个数。设f[i]表示到达第i个位置最小踩多少个石子.则f[i]=min(f[i-j]+d[i])(1<=i<=l+t)(s<=j<=t),d[i]表示第i个位置是否有石子.最后的答案就是在l to l+t 之间找最小。
虽然不知道怎么回事,但就是这个道理= =
上代码,我要抓紧写作业去
——春来遍是桃花水,不辨仙源何处寻。
版权声明:转载请注明出处 [ametake版权所有]欢迎来看
不要等待机会,而要创造机会。