漂亮打印与动规模型的建立(续)
题目如下:
由给定的n个英文单词组成一篇文章,每个单词的长度(字符个数)依次为l1,l2...要在一台打印机上将这段文章漂亮的打印出来.打印机每行最多可打印M个字符.这里说说的漂亮定义如下:在打印机所打印的每一行中,行首和行尾可不留空格;行中每两个单词之间可留一个空格;如果在一行中打印从单词i到单词j的字符,则按照打印规则,应该在一行中打印sum(li,i<=i<j)+j-i个字符,且不允许将单词打破多余的空格数为M-j+i-sum(li,i<=i<j);除文章的最后一行外,希望每行多余的空格数目尽可能少,以每行多余空格数的立方和达到最小作为漂亮的标准(最后一行不算).
比如M=5
a︻bc︻
d︻ef︻
g(最后一行不算)
︻表示空格 总空余为1*1*1+1*1*1=2
上一篇中说到了如何建立漂亮打印问题的动态规划模型。这一篇要说说如何缩减时间复杂度。
上次的代码循环部分如下
for(int j=1;j<=n;j++) {
c[j]=100000000;
for(int i=1;i<=j;i++)
if(c[i-1]+lc(i,j)<c[j]) {c[j]=c[i-1]+lc(i,j);p[j]=i;}
}
lc(I,j)的复杂度为O(j-i).所以总复杂度为O(sum(n2)) (1<=j<=n)=O(n3)。可不可以缩减复杂度呢?有!方法就是先算出lc(I,j) 1<=i<j的所有值,存在一张表lc[n][n]里,之后在循环内直接调用的开销仅为O(1)。但建表lc[n][n]的复杂度如果直接算也是n3。这里就可以进一步优化,我们用表e[i][j]来存放M减去i到j的字符数。再在lc(I,j)中对这个值的正负进行判断即可:若负,返回无穷;若正,再看j。而e[i][j]=e[i][j-1]-lj-1!又是一个漂亮的转换。这样根据e[i][j]的值再经O(1)操作即可返回值。
经过优化后,算法的时间复杂度降低为O(n2),进了一大步!
反思一下,为什么算法的时间复杂度降低了呢?本质还是进一步采用了动态规划的记忆原理。我们在算sum(I,j)(i到j的字符总和)的时候用到了sum(I,j-1)的值,因为sum(I,j)=sum(I,j-1)+1+lj。在未经优化时,我们把sum(I,j-1)又重算了一遍,所以时间复杂度大了。这就有点类似最大m子段和问题中的内部优化,第i行的状态依赖于i-1行的最优态,因此提前记录下来。所以说在动规算法的内部再进行记忆化处理,往往能得到更好的效果。
源代码如下:
//优化版本
#include<iostream>
using namespace std;
int m,n; //每行最大容量
int c[1000]; //状态数组
int l[1000];
int p[1000]; //保存记录用于重构最优解的数组
int e[1000][1000];
int lc(int i,int j) {
if(e[i][j]<0) return 10000000; //从i到j的单词不能放在一行
if(j==n) return 0; //最后一行
else return e[i][j]*e[i][j]*e[i][j];
}
void PrettyPainting() {
c[0]=0; //base case;
for(int j=1;j<=n;j++) {
c[j]=100000000;
for(int i=1;i<=j;i++)
if(c[i-1]+lc(i,j)<c[j]) {c[j]=c[i-1]+lc(i,j);p[j]=i;}
}
cout<<c[n];
}
int main()
{
int k,t;
//计算e[i][j]
for(k=1;k<=n;k++) {
e[k][k]=m-l[k];
for(t=k+1;t<=n;t++)
e[k][t]=e[k][t-1]-l[t]-1;
}
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>l[i];
PrettyPainting();
return 0;
}
PS:答案提供了一个思路可以将复杂度缩减到O(nM)。事实上,由于每一个单词最少都要占一个长度,所以一行最多能容纳num=((M/2)上取整)个单词,e[i][j]中只要计算i大于等于(j-num)对应的e[i][j]即可,,在计算c[i][j]时i也从(j-num)开始算即可。