#2363. 木梳

    ID: 2363 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>PROV赛事:contest4094来源:qoj.ac数据:公开样例动态规划

木梳

木梳

题目描述

第二题:木梳(程序文件名:comb.exe)100分,运行时限:1s 艾艺从小酷爱艺术,他梦想成为一名伟大的艺术 家。最近他获得了一块材质不错的木板,其下侧为直 线段,长为L,平均分为L 段,从左到右编号为1, 2,……,L。木板的上侧为锯齿形,高度为整数,第i 段 的高度为Ai,Ai>=2(如右图所示)。 这么好的一段材料浪费了怪可惜的,艾艺决定好 好加工一番做成一件艺术品。但他不是纯艺术家,他 觉得每件艺术品都应有实用价值(否则只是华而不 实),具有实用性的艺术品是他设计的理念。 根据这块木板的锯齿状,艾艺想到了每天起床后 L=9 A=(4,4,6,5,4,2,3,3,5) 1 2 3 4 5 6 7
8 9

2005-7-7 都要用到的一件日用品,“对,就把它做成梳子!”他的设想是:用刻刀将某些上端的格子挖掉 (如果把某个格子挖掉,那么这个格子上方的格子也必须被挖掉,但不能把一列中的格子全都挖 掉),使得剩下的木板构成“规则锯齿形”(这样才好梳头)。 例如,对上图,挖掉第3、7、8 列最上面的1 个格 子和第5 列最上面的2 个格子后,剩下的区域就构成 “规则锯齿形”(如右图所示)。一个锯齿形称为“规 则锯齿形”当且仅当它的上边界(右图中红色曲线所 示)的拐点序列不包含“010”或者“101”。右图中 红色曲线的拐点序列为:“011001”,(其中0 代表左 拐,1 代表右拐),沿着曲线的最左端往右走,先左拐, 再右拐,接着右拐,然后左拐,继续左拐,最后右拐。 为了最大限度地减少浪费,艾艺希望做出来的梳子面积最大。 【输入格式】(input.txt) 从文件input.txt中读入数据,文件第一行为整数L,其中4<=L<=100000,且有50%的数据满 足L<=104,表示木板下侧直线段的长。第二行为L个正整数A1,A2,…,AL,其中1<Ai<=108,表示第 i段的高度。 【输出格式】(output.txt) 输出文件output.txt 中仅包含一个整数D,表示为使梳子面积最大,需要从木板上挖掉的 格子数。 【输入输出样例】 input.txt output.txt 9 3 4 4 6 5 4 2 3 3 5(方案如右图所示)

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

9
4 4 6 5 4 2 3 3 5
3