回复 @TA :
那个标记其实不用管啦……不加优化也可以过的

还是贴一下90分的代码……这个没有考虑“第二阶段中进驻到首都的军队比最初部署到首都的军队更‘无用’”的情况……（太拗口……）
@chs

先用线段树水到85，丧心病狂地用读入优化+静态化搞到90……最后才知道差分序列有这种用法QAQ……果然自己太弱
借自己的楼临时贴一下90分的区间修改+区间查询的线段树…… @chs

丧心病狂的贪心……我会说我差点敲了个分治吗……
好吧其实证明的时候用到了数学归纳的思想……假设前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，
难道说清华大学一定比清华大学好，卧槽。

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