网站建议:179001057@qq.com

漂亮打印与动规模型的建立(续)

技术2022-05-11  1

漂亮打印与动规模型的建立(续)

题目如下:

    由给定的n个英文单词组成一篇文章,每个单词的长度(字符个数)依次为l1,l2...要在一台打印机上将这段文章漂亮的打印出来.打印机每行最多可打印M个字符.这里说说的漂亮定义如下:在打印机所打印的每一行中,行首和行尾可不留空格;行中每两个单词之间可留一个空格;如果在一行中打印从单词i到单词j的字符,则按照打印规则,应该在一行中打印sum(li,i<=i<j)+j-i个字符,且不允许将单词打破多余的空格数为M-j+i-sum(li,i<=i<j);除文章的最后一行外,希望每行多余的空格数目尽可能少,以每行多余空格数的立方和达到最小作为漂亮的标准(最后一行不算).

比如M=5

         abc

         def

         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减去ij的字符数。再在lc(I,j)中对这个值的正负进行判断即可:若负,返回无穷;若正,再看j。而e[i][j]=e[i][j-1]-lj-1!又是一个漂亮的转换。这样根据e[i][j]的值再经O(1)操作即可返回值。

         经过优化后,算法的时间复杂度降低为O(n2),进了一大步!

反思一下,为什么算法的时间复杂度降低了呢?本质还是进一步采用了动态规划的记忆原理。我们在算sum(I,j)ij的字符总和)的时候用到了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;    //ij的单词不能放在一行

         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)开始算即可。


最新回复(0)