题意:给出一个句子和要求整理后每行包含的字符数,要求将其整理为一种总badness最小的形式。设每个空格长度为n,单个空格的badness计算公式为(n-1)^2。总badness等于所有空格的badness的总和。给出整理后的格式。在badness最小的前提下,在分配一行中的空格时要让前面的空格尽量少。如果一个单词单占一行,badness为500。
分析:动态规划。f[i]表示前i个单词的最小badness是多少。f[i]=f[i-j]+cost(i-j,j);。cost(a,b)表示从单词a+1到单词b的放在一行中最小badness是多少。
并用from[i]存储f[i]是从哪个位置计算得来的值,即最后一次更新f[i]时i-j是几,即f[i]所在行的上一行的最后一个单词是第几个。
我们利用from数组可以求出最佳方案,然后按照题中要求输出即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = ; int n, wordsnum;
string words[maxn];
int sum[maxn];
int f[maxn][maxn];
int from[maxn][maxn]; void turntowords(string st)
{
int i = ; while ()
{
i = ;
while (st[i] != ' ' && i < signed(st.length()))
i++;
words[wordsnum++] = st.substr(, i);
sum[wordsnum] = i + sum[wordsnum - ];
if (i == signed(st.length()))
break;
st.erase(, i);
while (st[] == ' ')
st.erase(, );
}
} void init()
{
string st; wordsnum = ;
memset(sum, , sizeof(sum));
getchar();
while ()
{
getline(cin, st);
if (st == "")
break;
turntowords(st);
}
} int cost(int start, int end)
{
int left, right, tot, len; if (end - start == )
return ;
tot = n - (sum[end] - sum[start]);
len = tot / (end - start - );
left = end - start - - tot % (end - start - );
right = tot % (end - start - );
return left * (len - ) * (len - ) + right * len * len;
} void work()
{
int i, j, k; memset(f, -, sizeof(f));
f[][] = ;
for (i = ; i <= wordsnum; i++)
for (j = ; j <= wordsnum; j++)
for (k = ; k <= j && j - k >= i - && n - (sum[j] - sum[j - k]) >= k - ; k++)
if (f[i - ][j - k] != - && (f[i][j] > f[i - ][j - k] + cost(j - k, j) || f[i][j] == -))
{
f[i][j] = f[i - ][j - k] + cost(j - k, j);
from[i][j] = k;
}
} void printline(int start, int end)
{
int left, tot, len, i, j; if (end - start == )
{
cout << words[start] << endl;
return;
}
tot = n - (sum[end] - sum[start]);
len = tot / (end - start - );
left = end - start - - tot % (end - start - );
for (i = start; i < end - ; i++)
{
cout << words[i];
for (j = ; j < len; j++)
printf(" ");
if (i - start + > left)
printf(" ");
}
cout << words[end - ] << endl;
} void output()
{
int i, best = , besti; for (i = ; i <= wordsnum; i++)
if (f[i][wordsnum] < best && f[i][wordsnum] >= )
{
best = f[i][wordsnum];
besti = i;
}
int line[maxn];
int j = wordsnum;
for (i = besti; i > ; i--)
{
line[i] = from[i][j];
j -= from[i][j];
}
j = ;
for (i = ; i <= besti; i++)
{
printline(j, j + line[i]);
j += line[i];
}
cout << endl;
} int main()
{
//freopen("D:\\t.txt", "r", stdin);
while (cin >> n && n != )
{
init();
work();
output();
}
return ;
}