HBC15137文化节题解 (诗文赏析社采购的学生发现了一件事)

云中君 基本结构 122 0
题库丰富多样,涵盖各个领域,全网最全C++题库,让您在练习中不断成长!
一年一度的文化节快到了,诗文赏析社的同学想要举办她们自己创作的诗展,诗文赏析社的社长跟书法社的社长是好朋友,于是找来了一些书法社的同学帮忙书写诗文,一开始一切似乎都很顺利,但是负责采购的同学突然发现,用来写书法的纸实在是不便宜!注意在这个例子中,第一张纸不能是2 x 3,因为这样虽然写的下,但是不满足H1 = H3的条件, 现在,给定一首诗每行的长度,请问这种策略下,最少需要花费多少钱买纸呢?

一年一度的文化节快到了,诗文赏析社的同学想要举办她们自己创作的诗展。诗文赏析社的社长跟书法社的社长是好朋友,于是找来了一些书法社的同学帮忙书写诗文。一开始一切似乎都很顺利,但是负责采购的同学突然发现,用来写书法的纸实在是不便宜!这种纸的计价方式如下: 一首诗共有N 行,第i 行的长度为Li 个字,而纸只卖长方形的,所以一首诗如果要写在同一张纸上,则必须准备面积(行数 x 宽度) 为N x MAX(Li) 的纸。 1 单位面积的纸要价 1 元,虽然单位价格不高,但是对于长长的诗来说,这价格还是对学生不友善的。 于是,聪明的学生发现了一件事情,那就是,在她们创作的诗文中,通常只有连续的几行,长度特别长或特别短,而在其他的行里面,长度都不长也不短。因此,采购的学生决定,一首诗就分成三段,写在三张纸上好了!这三张纸分别为N1 x H1, N2 x H2 及N3 x H3,因为这三张纸的宽度很可能不会三者都必须要是MAX(Li) ,因此理论上可以省下不少钱! 但是,老板觉得,要准备三种宽度不同的纸实在是太麻烦了!所以黑心的老板给了另外一个规定,那就是 H1 必须要跟 H3 一样! 举例来说,假设一首六行诗文每行的长度依序为[3, 3, 7, 7, 4, 3],那第三张纸可以选择2 x 4, 2 x 7  及2 x 4 的纸,这样三张纸加起来只要30 元,比起单一一张6 x 7 的纸足足省下了12 元呢!注意在这个例子中,第一张纸不能是 2 x 3,因为这样虽然写的下,但是不满足 H1 = H3 的条件。 现在,给定一首诗每行的长度,请问这种策略下,最少需要花费多少钱买纸呢? 请注意,N1, N2 及 N3 这三个整数中,可以有一些是 0。 因为诗真的可能很长很长,所以输入的方式不会直接给出每行的长度,而是会给出一些generator的参数,用来产生出这些诗文每行的长度。关于generator的算法及参数请详阅输入说明。

全网最全C++题库,助您挑战自我,突破极限,成为编程领域的佼佼者!

标签: HBC15137文化节题解