本文共 2894 字,大约阅读时间需要 9 分钟。
题目描述
写电子邮件是有趣的,但不幸的是经常写不好看,主要是因为所有的行不一样长,你的上司想要发排版精美的电子邮件,你的任务是为他编写一个电子邮件排版程序。
完成这个任务最简单的办法是在太短的行中的单词之间插入空格,但这并不是最好的方法,考虑如下例子:
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,表示该段要求达到的宽度, 。该段文章由一个或多个单词组成,单词由ASCII码值为 到 (包含 和 )的字符组成,单词与单词之间用空格隔开(可能超过一个)。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过 个字符,任何一行都不会超过 个字符,任何一个单词都在同一行内。
输出描述
对于每个段落,找出使其难看程度最小的排版形式并输出句子:“Minimal badness is B.”,B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意,多余的空格也可删除。
样例输入
28This is the example you areactually considering.
样例输出
Minimal badness is 12.
Solve
二维的DP:
状态 表示第 个单词末尾放在 位置的最小难看程度
#include#define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define INF 0x7f7f7f7fconst int maxn=1e3+10;const int mod=1e9+7;using namespace std;char ch[maxn];// dp[i][j]表示第i个单词末尾放到位置j的最小难看程度int dp[maxn][maxn];int len[maxn];int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; int cnt=0; while(cin>>ch) len[++cnt]=strlen(ch); ms(dp,INF); dp[1][n]=500; dp[1][len[1]]=0; for(int i=2;i<=cnt;i++) for(int j=len[i];j<=n;j++) { int res=j-len[i]; // 如果是某行的第一个单词,继承上一行的最后一个状态 if(!res) dp[i][j]=dp[i-1][n]; else { if(j==n) dp[i][j]=dp[i-1][j]+500; for(int k=0;k
一维的DP
#include#define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define INF 0x7f7f7f7fconst int maxn=1e6+10;const int mod=1e9+7;using namespace std;char ch[maxn];// dp[i]表示以第i个单词作为一行的结尾的最小难看程度// dp[i]=min(dp[i]+cost(j,i))// cost(j,i)表示j+1到i在同一行的最小难看程度// 当空格在一行内平分的时候难看程度最小int dp[maxn];int len[maxn];inline int calc(int l,int r,int n){ if(l==r) { if(len[r]-len[l-1]==n) return 0; return 500; } // 一行内的空格数 int res=n-(len[r]-len[l-1]); // 一行内至少要有r-l个空格】 if(res >n; while(cin>>ch) len[++cnt]=len[cnt-1]+strlen(ch); ms(dp,INF); dp[0]=0; for(int i=1;i<=cnt;i++) for(int j=1;j<=i;j++) dp[i]=min(dp[i],dp[j-1]+calc(j,i,n)); cout<<"Minimal badness is "< <<"."<
转载地址:https://www.cnblogs.com/Friends-A/p/11054969.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!