文件排版(codevs 1300)
写电子邮件是有趣的,但不幸的是经常写不好看,主要是因为所有的行不一样长,你的上司想要发排版精美的电子邮件,你的任务是为他编写一个电子邮件排版程序。
完成这个任务最简单的办法是在太短的行中的单词之间插入空格,但这并不是最好的方法,考虑如下例子:
****************************
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,当然在这种情况下,该行的实际长度即为该单词的长度。
输入文件第一行是一个整数N,表示该段要求达到的宽度,1<=N<=80。该段文章由一个或多个单词组成,单词由ASCII码值为33到126(包含33和126)的字符组成,单词与单词之间用空格隔开(可能超过一个)。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过10000个字符,任何一行都不会超过100个字符,任何一个单词都在同一行内。
对于每个段落,找出使其难看程度最小的排版形式并输出句子:“Minimal badness is B.”,B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意,多余的空格也可删除。
28
This is the example you are
actually considering.
Minimal badness is 12.
/*
写了三维的DP,不知道那些二维是怎么做到的。
f[i][j]表示到了第i个单词,安排到了本行的第j位的方案数,然后枚举上一位放的位置进行转移。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10010
#define M 110
using namespace std;
int n,m,a[N],f[N][M];
char s[M];
int main(){
scanf("%d",&m);
while(scanf("%s",s)!=EOF)
a[++n]=strlen(s);
memset(f,/,sizeof(f));
f[][m]=;f[][a[]]=;
for(int i=;i<=n;i++)
for(int j=a[i];j<=m;j++){
int p=j-a[i];
if(!p) f[i][j]=f[i-][m];
else {
if(j==m) f[i][j]=f[i-][m]+;
for(int k=;k<p;k++)
f[i][j]=min(f[i][j],f[i-][k]+(p-k-)*(p-k-));
}
}
printf("Minimal badness is %d.",f[n][m]);
return ;
}
最新文章
- MVC复杂模型绑定
- QM模块包含主数据(Master data)和功能(functions)
- 安装.NET Framework后程序无法启动的错误处理
- live555库中的testRTSPClient实例
- Spring利用JDBCTemplate实现批量插入和返回id
- UIView 周围出现黑线的解决方法
- 将caffe训练时loss的变化曲线用matlab绘制出来
- 【BZOJ 2132】 圈地计划
- NODE编程(一)--Node功能的组织和重用
- 基于局部敏感哈希的协同过滤推荐算法之E^2LSH
- The Little Redis Book
- shutdown computer in ad and ou
- jquery-1.10.2 获取checkbox的checked属性总是undefined
- 简话ASP.NET Web API
- 第18天	ajax技术和javascript加强(json)
- 【转】NAS 黑群晖 配置完成(不含硬盘),NAS能做什么?
- 2.5 Cesium视域分析的实现
- LwIP Application Developers Manual8---Sample lwIP applications
- ceph集群性能测试结果
- Java中static、final、static final的区别【转】