noip积木大赛

先要覆盖一号位置的高度,(现在你的目的只是想要覆盖一号位置)。

每次你可以选区间[l,r]高度+1,这个作为一个操作。

为什么不选的范围大一点,让更多的区间增加高度呢。

所以红色的地方是,在我的目的是覆盖一号位置时,顺道全部覆盖的。

由于时间复杂度是O(n)的,接下来看2号位置,我的目的是要覆盖二号

位置,由于二号位置比一号位置高度小,那么在覆盖1号位置时,二号

位置已经覆盖了。再看三号位置,没有被覆盖完全,答案加上蓝色部分

后面同理。

原文地址:https://www.cnblogs.com/zzyh/p/7732405.html