给定由N个英文单词组成的一段文章,每个单词的长度(字符个数)依序为L1,L2,...Ln。我们要在一台打印机上将这段文章“漂亮地”打印机出来。打印机每行最多可打印M个字符。这里所说的“漂亮”的定义如下: 在打印机所打印的每一行中,行首和行尾可不留空格。行中每两个单词之间留一个空格。这样,如果在一行中打印从单词i到单词j的字符,则按打印规则,应在一行中恰好打∑L+j-i个字符(包括字符间空格),且不允许将单词打破。多余的空格数为M-j+i-∑L。除文章的最后一行外,希望每行多余的空格尽可能少。 因此,我们以各行(最后一行除外)的多余空格数的立方和达到最小作为“漂亮”的标准。
1