最新消息:点击查看大S的省钱秘笈

POJ 1653 Compacting Stickers C++版

POJ题解 Slyar 50浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

统计 + 枚举

Description

The text on a sticker consists of words formed from small and capital Latin letters. Words are separated by spaces, line breaks, and/or the following punctuation marks: ",", ".", "!", "?".

There may be any number of spaces and empty lines before and after the words, but there is no more than one punctuation mark after each word. Sticker is printed with monospace font, so every character occupies on the paper a rectangular area of fixed size. Sticker itself is a minimal rectangle enclosing the text plus a margin of one character in width.

Many copies of the sticker are to be printed, and to minimize paper consumption the sticker should be made as small in area as possible. Consider, for example, the sticker with the following text:
Our pink elephants have great size and a small price. Buy our elephants!

Printed in one line, this sticker will have an area of (72 + 2) * (1 + 2) = 222 characters. On the other hand, if printed in four lines, like this:

....................

.Our.pink.elephants.

.have.great.size....

.and.a.small.price..

.Buy.our.elephants!.

....................

the sticker will only require (18 + 2) * (4 + 2) = 120 characters.

You objective is, given the text of a sticker, to break it into lines so as to achieve the smallest possible area for it. Line break may be inserted after any word or punctuation mark, but not before a punctuation mark. One space must separate each word from the preceding word or punctuation on the same line. You do not have to preserve other spaces or line breaks in the input.

Input

The input contains one or more lines of the sticker text. The first line is an integer indicating the lines to follow. Text contains only the following characters: "A" to "Z", "a" to "z", ",", ".", "!", "?", spaces and line ends. The text length is less or equal than 10000 characters. The text always contains some non-space characters, and the first of them is always a letter.

Output

Output must contain a single integer number - the area of the smallest sticker.

Sample Input

Our     pink
Elephants
have great size and a
small  price    .
Buy our elephants !

Sample Output

120

Slyar:求合适的宽度和高度,使得放置所有单词后总面积最大。继续练习STL,使用了<algorithm>里的max_element和<vector>,感觉还不错。算法就是暴力枚举加一些剪枝,反正我就这么过了,具体看注释吧。很奇怪这道题交的人少,AC的人也少...

转载请注明:Slyar Home » POJ 1653 Compacting Stickers C++版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址