整齐打印

本文主要是介绍整齐打印，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考虑在一台打印机上优美地打印一段文章的问题。输入的正文是长度为I₁,I₂,…,I_n的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的单词所用的最少末尾空格。

这篇关于整齐打印的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---