# 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:

$M-j+i-\sum_{k=i}^{j}l_k$

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)3+(10−8)3+(10−7)3=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);
}