Printing Neatly

Consider the problem of neatly printing a paragraph with a monospaced font (all characters having the same width) on a printer. The input text is a sequence of n words of lengths l1, l2,…,ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of “neatness” is as follows. If a given line contains words i through j, where ij, and we leave exactly one space between words, the number of extra space characters at the end of the line is:


which must be nonnegative so that the words fit on the line. We wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph of n words neatly on a printer. The program MUST run in θ(Mn) and require θ(n) space.

Difficulty: Hard.


There are two lines.

  • The first line contains 2 integers separated by a space, which are n and M respectively.
  • The second line consists of n words separated by spaces.

At the end of each line, there are no extra spaces, and there is a \n.


One line containing 1 integer, which is the minimal total cost.



7 10

word like first as the the complete




The optimal printing:

word like
first as
the the

Since M is 10, the total cost is (10−9)3+(10−8)3+(10−7)3=36. Note that the last line shouldn’t be taken into account.

Solution: C++


#define MAX 100000000

using namespace std;

void print_neatly(std::string l[], int n, int M){
    int c[n+1]={0}; //cost of an optimal arrangement of words 1 to j
    for(int j=1;j<=n;j++){
        c[j] = MAX;
        for(int i=max(1,j-M/2+1);i<=j;i++){
            int aux = M-l[i-1].length(); //number of spaces in a line containing words from i to j
            for(int h=i;h<j;h++)
                aux = aux-l[h].length()-1; //subtract length of the word j plus one space
            int lc; //cost of including a line containing words from i to j
            if(aux<0) //too many words
                lc = MAX;
            else if(j-1==n-1 && aux>=0) //last line doesn't count
                lc = 0;
                lc = aux * aux * aux; //compute the cost for a line
                c[j] = c[i-1]+lc; //find the optimal solution

int main(){
    int n;
    cin>>n; //number of words
    int M;
    cin>>M; //maximum character per line
    std::string w[n];
    for(int i=0; i<n; i++)


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s