bzoj#P1200. [HNOI2005]木梳

[HNOI2005]木梳

题目背景

King从小就酷爱艺术,他梦想成为一名伟大的艺术家。

最近他得到了一块材质不错的木板,木板下侧为直线段,长为 LL ,平均分为 LL 段,从左到右编号为 1,2,...,L1,2,...,L

木板的上侧是锯齿形,高度为整数,第 ii 段的高度为 AiA_i。(如下图所示)

这么好的一段材料浪费了怪可惜的,King决定好好加工一番做成一件艺术品。但他不是纯艺术家,他觉得每一件作 品都应该有实用价值(否则只是华而不实),具有实用性的艺术品是他设计的理念。

根据这块木板的锯齿状,King想到了每天起床后都要用到的一件日用品,「对,就把它做成梳子!」他的设想是:用刻刀将某些上端的格子挖掉(如果把某个格子挖掉,那么这个格子上方的格子也必须被挖掉,但不能把一列中的格子全都挖掉),使得剩下木板构成「规则锯齿形」(这样才好梳头)。

例如,对于上图,挖掉第 378 列最上面 11 个格子,第 5 列最上面 22 个格子后,剩下的区域就构成「规则锯齿形」(如右图)。一个锯齿形称为“规则锯齿形”当且仅当它的上边界(图中红色曲线所示)的拐弯序列不包含 010 或者 101。图中红色曲线的拐弯序列为:011001,(其中 0 代表往左拐,1 代表往右拐)沿着曲线的最左端往右走,先左拐,再右拐,接着右拐,然后左拐,继续左拐,最后右拐。为了最大限度的减少浪费,King希望做出来的梳子面积最大。这样一来,设计梳子的任务就变得非常复杂了。

不过这是对于艺术家来说,对于你来说,不就是小菜一碟吗?

输入格式

第一行为整数 LL ,表示木板下侧直线段的长。 第二行为 LL 个正整数 A1,A2,,ALA_1,A_2,…,A_L

输出格式

仅包含一个整数 DD,表示为使梳子面积最大,需要从木板上挖掉的格子数。

样例输入

9
4 4 6 5 4 2 3 3 5

样例输出

3

数据范围

对于 100%100\% 的数据,4L1000004 \le L \le 100000Ai2A_i \ge 2

题目来源

HNOI 2005\texttt{HNOI 2005}