最大化用字母r完成的行数

我只是想知道我在之前的算法测试中遇到的问题.问题是关于一个男孩写作和散文.他希望最大化以'r'结尾的行数,因为他认为这会在他的论文中产生更高的等级(什么......).

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

例如,如果约束为10-15而不是72-80,则格式如下所示:

123456789012345

The slow blue  
dog is  
entertaining

是否有一种有效的算法可以在保持72-80字母约束的同时最大化以字母"r"结尾的行数？我们不能剪切整个单词以便以"r"结尾.

我尝试使用的算法做到了这一点:

从72开始检查当前行的72-80是否为字母"r".

如果72-80中没有字母"r",我们只是尝试尽可能地填写该行,然后转到下一行.

如果在72-80中有一个字母"r",我们将结束该行.

重复1直到没有更多行.

我对这个贪婪算法的主要问题是第2步.尽可能多地填充该行有可能在"r"中结束未来的结束行.

使用具有10-15约束的此算法将得到:

123456789012345
The man was in 
the backgarden  
or the yard

但最佳解决方案是:

123456789012345
The man was 
in the 
backgarden or 
the yard

:(