丧心病狂的贪心……我会说我差点敲了个分治吗……
好吧其实证明的时候用到了数学归纳的思想……假设前n个都已经盖成，此时若$h_i \geq h_{i+1}$，那么我们只需要在前面覆盖i点时多往后覆盖一格就可以了……但如果$h_i < h_{i+1}$，因为每次只能增加一个积木，而覆盖的区间又必须连续，那么这时我们至少要多进行$h_{i+1} - h_i$次操作= =
然后空间复杂度就可以果断$O(1)$了……

又见五星神题……

kmp算法 详解请看http://blog.sina.com.cn/s/blog_13a7287f40102v4vh.html

我感觉像记忆化搜索？？？？？

单调队列优化DP。 不过数据比较水， O(n^3) 都秒过

回复 @柚子冰 :
尽管数组开得太大导致IDE崩溃无法编译，我还是过了

开bool型爆不了yooooooo

回复 @传奇 :
炫迈........

为什么我的程序超时？到1秒了还停不下来

我什么都不说

每次都忘了ansistring，QAQ~~~~~~

楼上注意题意，不论什么数据，答案至少为1，因为一个数据必满足单调递减。

整齐的代码，我喜欢。。COGS 300T，1500留念。。

回复 @奶猹 :
我也喜欢

1 1
1
怎莫会输出1，
难道说清华大学一定比清华大学好，卧槽。

要不要这么残暴…………交了这么多回，总是跪…………

改题路漫漫…

再一次2B的在printf里加了&……

数论法法塔你啪不啪……