algorithm - 最大化以字母 r 结尾的行数

Question

我只是想知道我在之前的算法测试中遇到的一个问题。问题是关于一个男孩的写作和论文。他想最大限度地增加以“r”结尾的行数，因为他觉得这会导致他的论文获得更高的分数(什么......)。

无论如何，论文的限制是每行的最后 72-80 个字符需要有一个字母，除非包含下一个单词会超过一行中的 80 个字符(例如，我们可以有一个没有字母的行72-80 个字符点(如果添加下一个单词会使该行有 80 多个字符)或者它是最后一行(最后一行可以少于 72 个字符)。

例如，如果约束是 10-15 而不是 72-80，格式将如下所示:

123456789012345

The slow blue  
dog is  
entertaining

是否有一种有效的算法可以在保持 72-80 个字母限制的同时最大化以字母“r”结尾的行数？我们不能剪切整个单词以生成以“r”结尾的行。

我尝试使用的算法是这样做的:

1. 检查当前行的第 72-80 行是否有从 72 开始的字母“r”。
2. 如果72-80中没有字母“r”，我们就尽量填满这一行，然后转到下一行。
3. 如果72-80中有字母“r”，我们就结束这一行。
4. 重复 1 直到没有更多行。

我对这个贪心算法的主要问题是第 2 步。尽可能多地填充该行有可能防止 future 以“r”结尾的行。

将此算法与 10-15 约束一起使用将得到:

123456789012345
The man was in 
the backgarden  
or the yard

但最佳解决方案是:

123456789012345
The man was 
in the 
backgarden or 
the yard

:(

Answer 1

这可以通过动态规划解决方案来完成。

给文本中的每个单词一个分数，如果文本以该单词开头(即，如果您删除了它之前的所有内容)，则该分数是可能以“r”结尾的行数的最大值。

因此，例如，最后一个单词的分数将为 0 或 1(取决于它是否以“r”结尾)。第一个单词的分数就是你需要的答案。

从最后到第一个单词计算分数。对于给定的单词，分析所有可能性以创建第一行。对于给定的可能性，分数将是第二行中第一个单词的分数，如果第一行以“r”结尾则加 1。给定单词的分数将是最佳可能性的分数。

使用示例文本“那个人在后花园或院子里”:

yard: score 0
the: score 0
or: score 0 (only possibility for first line is "or the yard")
backgarden: score 1 (there are two possibilities for first line, the better one
                     is "backgarden or" which gives the score of "the" plus 1).
the: score 0 (only possibility for first line is "the backgarden")
in: score 1 (first line is "in the" which gives the score of "backgarden")
was: score 1
man: score 1 (first line is either "man was in" or "man was in the". The second
              option gives the score of "backgarden" which is 1.
The: score 1 (best first line is "The man was" which gives the score of "in").

计算分数后，要构建最佳的行分隔文本，请从第一个单词开始，为第一行选择最佳可能性(如上所述)，然后重复下一行的第一个单词。