/**
* 由给定的n个英文单词组成一篇文章，每个单词的长度(字符个数)依次为l1,l2...
* 要在一台打印机上将这段文章漂亮的打印出来．打印机每行最多可打印M个字符．
* 这里所说的漂亮打印定义如下：
* 在打印机所打印的每一行中，行首和行尾可不留空格；
* 行中每两个单词之间留一个空格，且不允许将单词打破。
* 如果在一行中打印从单词i到单词j的字符，则按照打印规则，应该在一行中打印
* sum(lk,i<=k * 除文章的最后一行外，希望每行多余的空格数目尽可能少，
* 以每行多余空格数的立方和达到最小作为漂亮的标准．
* 分析与解答：
* 最优子结构性质：
* 在一个最优打印方案上，如果将单词1～k安排在第一行打印，则
* 显然这个方案对后续的k+1～n个单词的打印安排是单词k+1~n的漂亮打印子问题的
* 最优打印方案重叠的子问题：
* 在第一行中安排单词1~k的所有打印方案都要考虑后续单词k+1~n的打印子问题．
* 因此，在计算中有许多重叠子问题递归计算：
* 由于在一行不允许将单词打破，故可设li<=M,1<=i<=n．
* 为了处理边界情形，定义数组extras和lc如下：
* extras[i][j]=M-j+i-sum(lk,i<=k * 它是将单词i到j安排在一行中时行尾的多余空格数．
* 注意extras[i][j]可能为负，即一行不够打印i~j，有可能将单词打破．
* lc表示将单词i~j打印在一行上的费用：
* ┌∞ if (extras[i][j]<0)
* lc[i][j]=│0 if (extras[i][j]>=0 && j=n)
* └(extras[i][j])^3 else
* 设c[i]是安排单词1～i时候的最小费用，则递归的计算如下：
* ┌0 i=0;
* c[i]=│
* └min{c[j-1]+lc[j][i],1<=j<=i} i>0;
*/
#include
#include
#define N 100
#define INF 10000
void print(int *p, int n)
{
int i,j;
for (i=0;i {
for (j=0;j printf("\t");
for (j=i;j printf("%8d",*(p+i*N+j));
printf("\n");
}
}
int main()
{
int i,j;
int n,m;
int min,tmp_min,tmp_idx;
int l[N];
int sum[N][N];
int extras[N][N];
int lc[N][N];
int c[N+1],idx[N];
printf("输入——文章中总共有多少个单词：");
scanf("%d",&n);
for (i=0;i {
printf("输入——第%2d个单词的长度是多少：",i+1);
scanf("%d",l+i);
}
printf("输入——每行可以打印多少个字符：");
scanf("%d",&m);
for (i=0;i sum[i][i] = l[i];
for (i=1;i for (j=0;j sum[j][i] = sum[j][i-1]+l[i];
print((int*)sum, n);
for (i=0;i for (j=i;j extras[i][j] = m+i-j-sum[i][j];
print((int*)extras, n);
for (i=0;i for (j=i;j if (extras[i][j]<0)
lc[i][j] = INF;
else if (j==n-1)
lc[i][j] = 0;
else
lc[i][j] = extras[i][j]*extras[i][j]*extras[i][j];
print((int*)lc, n);
c[n] = 0;
for (i=n-1;i>=0;i--)
{
min = INF;
for (j=i+1;j<=n;j++)
{
tmp_min = lc[i][j-1]+c[j];
if (min>tmp_min)
{
min = tmp_min;
tmp_idx = j-1;
}
}
c[i] = min;
idx[i] = tmp_idx;
}
printf("漂亮打印的空格立方和：%d\n", c[0]);
printf("漂亮打印如下：\n");
printf("|");
for (i=0;i printf("-");
printf("|\n|");
tmp_idx = 0;
for (i=0;i {
for (j=0;j printf("*");
if (idx[tmp_idx]==i)
{
for (int k=0;k printf(" ");
printf("|\n|");
tmp_idx = i+1;
}
else
printf(" ");
}
for (i=0;i printf("-");
printf("|\n");
system("pause");
return 0;
}
