考虑在一台打印机上优美地打印一段文章的问题。输入的正文是长度为I1,I2,…,In的n个单词构成的序列。我们希望将这段文章在几行上打印出来，每行的最大长度为m，且“优美”度的标准如下:
如果某一行包含从i到j的单词，且每两个单词间留一空，则在行末多余的空格为
我们希望除最后一行的所有行中，行末多余空格的总和最小。请给出一个算法来优美地打印出一段有n个单词的文章。
由于必须打印完n个单词且每行打印的单词是连续的，因此，我们从第n个单词开始，依次考虑填一个单词(单词n)，填两个单词(单词n-1，单词n)…，填n个单词(单词1，单词2，…，单词n)的打印方案。
r[i]
设当前行填入单词i…单词j(i≤ j)，每两个单词间留一空，单词间的空格数为j一i，从第i个单词到第j个单词的长度和为
，因此行末多余的空格为
。由于单词填人的方式是按单词序号递减的顺序进行的，因此填入单词i…单词n后的行末空格数的总和应为当前行的行末空格数+前面行的行末空格数的和。我们的目标是使它最小。
设 r[i] -- 填入单词i…单词n后，所有被填行的行末空格数总和的最小值。显然，r[i]的递归式如下：
另外，我们专门设置了一张记忆表k[i](1≤ i≤ n+1)，记下使得r[i]最小的j值，表示填单词i…单词n的最佳方案中，最后一行应填单词i…单词j(=k[i])。
r的递归的边界为
r[n+1]=0；k[n+1]=n+1；
表示不填任何单词时的行末空格数为0。
我们从r[n+1]出发，依次求r[n],r[n-1]…r[1]。由r[i]的递归式可以看出，求 r[i]最小值的子问题，包含了求r[i+l]…r[n+l]的子问题。要使r[i]最小，必须使这些子问题的值最小，因此符合动态规划程序设计要求的“最优子结构”和“重叠子问题”两个要素。我们按自下而上的方式求解，充分利用了重叠子问题。最后求出的r[1]为优美打印方案中行末空格数的总和；从单词1出发，顺着记忆表K的指示，可顺序打印出文章的各行。
网上的代码（个人认为有些问题，因为最后一行要特殊处理）：
/*优美打印 见算法导论
要在每行长度为m的纸上打印n个长为l[i]的单词，优美的定义是：同行单词空一个，使各行末尾空格之和（最后一行除外）最小。
逆填单词，设r[i]表示打印i到第n个单词的最小末尾空格数，显然，r[i]的递归式如下：
r[i]=min(m-((j-i)+sum[i][j])+r[j+1])(1<=i<=n+1)(i<=j<=n)
我们专门设置了一张记忆表k[i](1≤i≤n+1)，记下使得r[i]最小的j值
边界条件r[n+1]=0;k[n+1]=n+1;
*/
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n,m;
int l[101],c[101][101],sum[101],r[101],k[101];
//第i个单词长l[i]，前i个单词长sum[i]，k记录
const int INF=1000000000;
int PERFECT_PRINT()
{
r[n+1]=0,k[n+1]=n+1;
for(int i=1;i<=n;i++)r[i]=INF;
for(int i=n;i>=1;i--)
{
for(int j=n;j>=i;j--)
{
if(m<j-i+c[i][j])continue;
int tmp=m-((j-i+c[i][j]))+r[j+1];
if(tmp<r[i]){r[i]=tmp;k[i]=j;}
}
}
return r[1];
}
void print()
{
cout<<PERFECT_PRINT()<<endl;
int p=1;
while(1)
{
if(p==n+1)break;
cout<<k[p]<<" ";
p=k[p]+1;
}
cout<<endl;
}
int main()
{
while(cin>>n>>m)
{
for(int i=1;i<=n;i++)cin>>l[i];
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+l[i];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
c[i][j]=sum[j]-sum[i-1];
print();
}
}
我大概写了一下思路，有些边界条件没有处理
const int N = 7;
int a[] = {0,1,4,8,2,4,1};
int b[N];
int c[N][N];
int s[N];
int r[N];
int m = 10;
int neatPrint() {
memset(s,0,sizeof(s));
int i = 0;
for (i = 1; i <= N-1; ++i)
s[i] += s[i-1] + a[i];
for( i = 1; i < N; ++i) {
for (int j = 1; j < N; ++j) {
if( i<= j )
c[i][j] = s[j] - s[i-1];
}
}
for( i = N-1; i >0; --i) {
if (c[i][N-1] + N - 1 - i <=m) {
b[i] = N-1;
r[i] = 0;
}
}
if (i >1) {
for (;i >0; --i) {
for (int j = N-1;j>=i; --j) {
if (m - (j - i + c[i][j]) >=0) {
int tmp = m - (j - i + c[i][j]) + r[j+1];
if (tmp < r[i]) {
r[i] = tmp;
b[i] = j;
}
}
}
}
}
}
从最后一个单词开始放，r[i]表示在以i单词开头的文档，从i到N的单词所用的最少末尾空格。