西安至成网站建设公司,怎么用安卓机顶盒做网站服务器,wordpress精品主题,网站内页收录突然没了1300 文件排版 时间限制: 1 s
空间限制: 128000 KB
题目描述 Description
写电子邮件是有趣的#xff0c;但不幸的是经常写不好看#xff0c;主要是因为所有的行不一样长#xff0c;你的上司想要发排版精美的电子邮件#xff0c;你的任务是为他编写一个电子邮件排版程序…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程序的目的是使难看程度的总和最小化。例如第一个例子的难看程度是17*750而第二个例子的难看程度仅为11141412。
输出时每一行的开头和结尾处都必须是一个单词即每行开头和结尾处不能有空白。唯一例外的是该行仅有一个单词组成的情况对于这种情况你可将单词放在该行开头处输出此时如果该单词比该行应有的长度短则我们指定它的最坏程度为500当然在这种情况下该行的实际长度即为该单词的长度。
输入描述 Input Description
输入文件第一行是一个整数N表示该段要求达到的宽度1N80。该段文章由一个或多个单词组成单词由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]f[i]f[i] 转移方程为 f[i]min(f[i],f[j−1]cost(j,i));f[i] min(f[i],f[j-1]cost(j,i));f[i]min(f[i],f[j−1]cost(j,i)); cost(j,i)cost(j,i)cost(j,i)为平均化j~i号词的花费
#includecstdio
#includecmath
#includecstring
#includeiostream
#includealgorithm
#includeclimitsusing namespace std;
typedef long long ll;
const int maxn 0x3f3f3f3f;
char a[110];
int sum[10010],n;
ll dp[10010];
int cost(int i,int j){if(!(i^j)){if(!((sum[i]-sum[j-1])^n))return 0;return 500;}int blank n-(sum[i]-sum[j-1]);int num i-j;//分割数量if(blanknum)return maxn;int avg blank/num;int y blank-avg*num;avg--;return num*1LL*(avg)*(avg)1LL*y*(avg1|1);
}
int main()
{int cnt1;scanf(%d,n);while(~scanf(%s,a)){sum[cnt] sum[cnt-1]strlen(a);cnt;}for(int i1;icnt;i)dp[i] maxn;for(int i1;icnt-1;i){for(int j1;ji;j){dp[i] min(dp[i],dp[j-1]cost(i,j));}}printf(Minimal badness is %lld.\n,dp[cnt-1]);return 0;
}
