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 l₁, l₂,…,l_n, 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 i≤j, 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.

Input

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.

Output

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

Example

Input:

7 10

word like first as the the complete

Output:

36

Explanation:

The optimal printing:

word like
first as
the the
complete

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

Solution: C++

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<string>

#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;
            else
                lc = aux * aux * aux; //compute the cost for a line
            if(c[i-1]+lc<c[j]){
                c[j] = c[i-1]+lc; //find the optimal solution
            }
        }
    }
    cout<<c[n];
}

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++)
        cin>>w[i];
    print_neatly(w,n,M);
}

References

• Viterbiweb solution