题目描述
写电子邮件是有趣的，但不幸的是经常写不好看，主要是因为所有的行不一样长，你的上司想要发排版精美的电子邮件，你的任务是为他编写一个电子邮件排版程序。
完成这个任务最简单的办法是在太短的行中的单词之间插入空格，但这并不是最好的方法，考虑如下例子：
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\times7=50$，而第二个例子的难看程度仅为$1+1+1+4+1+4=12$。
输出时，每一行的开头和结尾处都必须是一个单词，即每行开头和结尾处不能有空白。唯一例外的是该行仅有一个单词组成的情况，对于这种情况你可将单词放在该行开头处输出，此时如果该单词比该行应有的长度短则我们指定它的最坏程度为$500$，当然在这种情况下，该行的实际长度即为该单词的长度。
输入描述
输入文件第一行是一个整数N，表示该段要求达到的宽度，$1\leq N\leq 80$。该段文章由一个或多个单词组成，单词由ASCII码值为$33$到$126$（包含$33$和$126$）的字符组成，单词与单词之间用空格隔开（可能超过一个）。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过$10000$个字符，任何一行都不会超过$100$个字符，任何一个单词都在同一行内。
输出描述
对于每个段落，找出使其难看程度最小的排版形式并输出句子：“Minimal badness is B.”,B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意，多余的空格也可删除。
样例输入
1
2
3
4
| 28
This is the example you are
actually considering.
|
样例输出
Solve
二维的DP：
状态$dp[i][j]$表示第$i$个单词末尾放在$j$位置的最小难看程度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x7f7f7f7f
const int maxn=1e3+10;
const int mod=1e9+7;
using namespace std;
char ch[maxn];
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<res;k++)
dp[i][j]=min(dp[i][j],dp[i-1][k]+(res-k-1)*(res-k-1));
}
}
cout<<"Minimal badness is "<<dp[cnt][n]<<"."<<endl;
return 0;
}
|
一维的DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x7f7f7f7f
const int maxn=1e6+10;
const int mod=1e9+7;
using namespace std;
char ch[maxn];
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]);
if(res<r-l)
return INF;
int space=res/(r-l);
int more=res%(r-l);
space-=1;
return space*space*(r-l)+more*(space*2+1);
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
int cnt=0;
cin>>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 "<<dp[cnt]<<"."<<endl;
return 0;
}
|