几个有难度的题目

边走¤边爱

几个挺难的c++题目


(1.)Description
艾艺从小酷爱艺术，他梦想成为一名伟大的艺术家。最近他获得了一块材质不错的木板，其下侧为直线段，长为L，平均分为L段，从左到右编号为1，2，……， L。木板的上侧为锯齿形，高度为整数，第i段的高度为Ai，Ai>=2（如右图所示）。这么好的一段材料浪费了怪可惜的，艾艺决定好好加工一番做成一件艺术品。但他不是纯艺术家，他觉得每件艺术品都应有实用价值（否则只是华而不实），具有实 用性的艺术品是他设计的理念。根据这块木板的锯齿状，艾艺想到了每天起床后都要用到的一件日用品，“对，就把它做成梳子！”他的设想是：用刻刀将某些上端的格子挖掉（如果把某个格子挖 掉，那么这个格子上方的格子也必须被挖掉，但不能把一列中的格子全都挖掉），使得剩下的木板构成“规则锯齿形”（这样才好梳头）。 例如，对上图，挖掉第3、7、8列最上面的1个格子和第5列最上面的2个格子后，剩下的区域就构成“规则锯齿形”（如右图所示）。一个锯齿形称为“规则锯 齿形”当且仅当它的上边界（右图中红色曲线所示）的拐点序列不包含“010”或者“101”。右图中红色曲线的拐点序列为：“011001”，（其中0代 表左拐，1代表右拐），沿着曲线的最左端往右走，先左拐，再右拐，接着右拐，然后左拐，继续左拐，最后右拐。为了最大限度地减少浪费，艾艺希望做出来的梳子面积最大。
Input
多组测试数据 文件第一行为整数L，其中4<=L<=100000，表示木板下侧直线段的长。第二行为L个正整数A1,A2,…,AL，其中1<=108，表示第i段的高度。 以0为结束标志.
Output
对于每组测试数据 仅包含一个整数D，表示为使梳子面积最大，需要从木板上挖掉的格子数。
Sample Input
9
4 4 6 5 4 2 3 3 5
0
Sample Out