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

    技术2022-05-11  26

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

    题目如下:

        由给定的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)