Codeforce 1491C Pekora and Trampoline（思维+差分）

Codeforce 1491C Pekora and Trampoline（思维+差分）

​​题目链接​​

题目大意： 有n个跳床，每个跳床有一个跳的距离，每个跳床跳一次就会使得弹跳距离减1，弹跳距离max(1,a[i])。你可以选择任意跳床选择开始，问你最少经过几个轮回才能将所有跳床弹跳距离都变成1。

思路： 差分维护 首先我们要将全部都转化成1，那么最优的方法就是从第一个大于1的弹床开始跳，这样一定是最优的。我们假设第一个是a[i]，那么他第一次跳到(i+a[i])上，第二次跳到(i+a[i]-1)…知道最后一次从i点开始跳就跳到(i+2)上。一共跳了(a[i]-1)次。 注意这个地方：其实就是来积累前面跳到这个地方的.

if(tmp<1) { if(i+1<=n) { b[i+1]+=(1-tmp);///会前面变1走的次数 } if(i+2<=n) { b[i+2]-=(1-tmp);///后端维护了 }}

#include #include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。