首页 > 代码库 > codevs 1300 文件排版

codevs 1300 文件排版

1300 文件排版

 时间限制: 1 s
 空间限制: 128000 KB
 
题目描述 Description

写电子邮件是有趣的,但不幸的是经常写不好看,主要是因为所有的行不一样长,你的上司想要发排版精美的电子邮件,你的任务是为他编写一个电子邮件排版程序。

完成这个任务最简单的办法是在太短的行中的单词之间插入空格,但这并不是最好的方法,考虑如下例子:

****************************

This is the example you  are

actually considering.

假设我们想将第二行变得和第一行一样长,靠简单地插入空格则我们将得到如下结果:

****************************

This is the example you  are

actually        considering.

 

但这太难看了,因为在第二行中有一个非常大的空白,如果将第一行的单词“are”移到下一行我们将得到较好的结果:

****************************

This  is  the  example   you

are  actually   considering.

 

当然,这必须对难看程度进行量化。因此我们必须给出单词之间的空格的难看程度,一个包含N个空格符的空白段,其难看程度值为(n-1)2,程序的目的是使难看程度的总和最小化。例如,第一个例子的难看程度是1+7*7=50,而第二个例子的难看程度仅为1+1+1+4+1+4=12。

输出时,每一行的开头和结尾处都必须是一个单词,即每行开头和结尾处不能有空白。唯一例外的是该行仅有一个单词组成的情况,对于这种情况你可将单词放在该行开头处输出,此时如果该单词比该行应有的长度短则我们指定它的最坏程度为500,当然在这种情况下,该行的实际长度即为该单词的长度。

输入描述 Input Description

输入文件第一行是一个整数N,表示该段要求达到的宽度,1<=N<=80。该段文章由一个或多个单词组成,单词由ASCII码值为33到126(包含33和126)的字符组成,单词与单词之间用空格隔开(可能超过一个)。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过10000个字符,任何一行都不会超过100个字符,任何一个单词都在同一行内。

输出描述 Output Description

对于每个段落,找出使其难看程度最小的排版形式并输出句子:“Minimal badness is B.”,B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意,多余的空格也可删除。

 

样例输入 Sample Input

28

This is the example you  are

actually considering.

样例输出 Sample Output

Minimal badness is 12.

 

令f[i]表示第i个单词放在当前行最后的最小最小难看程度

状态转移:f[i]=min(f[j-1]+cost(j,i)]) 1<=j<=i

cost(j,i):单词j——i在同一行的最小难看程度

当i==j时,如果单词长度=n,cost=0,否则=500

 

预处理了cost版 

其实没有必要预处理,每个cost只会用一次

#include<cstdio>#include<cstring>#include<algorithm>#define inf 0x3f3f3f3fusing namespace std;char str[101];int len[5001],cnt,n;int cost[5001][5001],sum[5001],f[5001];int main(){    scanf("%d",&n);    while(scanf("%s",str)!=EOF)      len[++cnt]=strlen(str);    for(int i=1;i<=cnt;i++) sum[i]=sum[i-1]+len[i];    int space,part,x,y,z,tot;    memset(cost,-1,sizeof(cost));    for(int i=1;i<cnt;i++)     for(int j=i+1;j<=cnt;j++)      {           space=n-(sum[j]-sum[i-1]);//空格总数            if(space<=0) break;         part=j-i+1-1; //分成的部分数            x=space/part;//平均每部分多少 取整         if(!x) break;         y=space-part*x;//多出的         z=part-y;//恰好平均的          tot=z*(x-1)*(x-1)+y*x*x;         cost[i][j]=tot;       }    for(int i=1;i<=cnt;i++)     {        if(len[i]==n) cost[i][i]=0;        else cost[i][i]=500;    }    for(int i=1;i<=cnt;i++) f[i]=inf;    for(int i=1;i<=cnt;i++)     for(int j=1;j<=i;j++)      if(cost[j][i]!=-1)      f[i]=min(f[i],cost[j][i]+f[j-1]);    printf("Minimal badness is %d.",f[cnt]);}

不预处理,时间与空间均优于上面

#include<cstdio>#include<cstring>#include<algorithm>#define inf 0x3f3f3f3fusing namespace std;char str[101];int cnt,n,sum[5001],f[5001];int cal(int i,int j){    if(i==j) return sum[j]-sum[i-1]== n ? 0 : 500;    int t=n-(sum[j]-sum[i-1]);    if(t<j-i) return inf;    int x=t/(j-i),y=t-(j-i)*x; x--;    return (j-i)*x*x+y*(x<<1|1);}int main(){    scanf("%d",&n);    while(scanf("%s",str)!=EOF) sum[++cnt]=sum[cnt-1]+strlen(str);    for(int i=1;i<=cnt;i++) f[i]=inf;    for(int i=1;i<=cnt;i++)     for(int j=1;j<=i;j++)      f[i]=min(f[i],f[j-1]+cal(j,i));    printf("Minimal badness is %d.",f[cnt]);}

 

codevs 1300 文件排版