/*
 *  poj 1093 Formatting Text

    数学模型:
        f[i]是以第i个单词为某行首，i到最后一个单词组成段落所能取得最小badness。
        
        枚举与i同行的单词个数k，则有如下递归式成立:

        f(i) = min{f(i+k) + best_bad(i, i+k-1) | k->1 to m}

        其中best_bad(i, i+k-1)表示从第i个单词(包含)起k个单词组成的行，所能取得的最小badness。

        关于best_bad的求法，可以采用如下公式求解:

            best_bad(i, i+k-1) = (space_num/(k-1))^2 * (k-1) + (2*(space_num/(k-1)) + 1)*(space_num%(k-1))

        其中:
            space_num = [n - sum{len(j) | j->i to i+k-1} - (k-1)];

        关于本求法的证明有如下引理:
            假设x+y=z，且有x'=x-t, y'=y+t则x^2+y^2 < x'^2+y'^2。-- 和一定的情况下，因子越是接近平均数，则其平方和越小。

        证明:
            x'^2 + y'^2 = (x-t)^2 + (y+t)^2
                        = x^2 + y^2 + 2t^2 + 2(y-x)t
                        > x^2 + y^2
    
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

namespace {
    using namespace std;

    const int INFINITY = 0x7fffffff; // 正无穷

    const int N_MAX = 10000; // 单词个数最大值
    const int W_MAX = 80; // 行宽最大值
    
    int length[N_MAX+1]; // 每个单词的长度
    
    char words[N_MAX+1][W_MAX]; // 单词存储
    
    int L; // 指定行宽
    int n = 0; // 单词个数

    int f[N_MAX+1];
    int count[N_MAX+1];
    int space[N_MAX+1];

    void print(int no)
    {
        if (count[no]==1) // 只有一个单词的情况，直接输出
        {
            printf("%s\n", words[no]);
        }
        else
        {
            // 计算各单词间的空格数
            int spacenum, num;
            char space_format[16]; // 空格输出格式字符串
            
            spacenum = space[no]/(count[no]-1)+1;
            num = (count[no]-1) - space[no]%(count[no]-1);

            sprintf(space_format, "%%s%%%ds", spacenum);
            int i=0;
            for (; i<num; i++)
            {
                printf(space_format, words[no+i], " ");
            }

            sprintf(space_format, "%%s%%%ds", spacenum+1);
            for (; i<(count[no]-1); i++)
            {
                printf(space_format, words[no+i], " ");
            }
            printf("%s\n", words[no+count[no]-1]); // 输出最后一个单词
        }

        if (no+count[no] != n) // 输出后面的段落
        {
            print(no+count[no]);
        }
            
        return;
    }
    
    #define square(x) \
        ((x)*(x))

    void format_text()
    {
        f[n] = 0;
        for (int i=n-1; i>=0; i--) // 从后向前求解，因为模型中前面的依赖后面的
        {
            // 该行只有word[i]一个单词的情况
            int curlen = length[i];
            f[i] = f[i+1] + 500; // 只有一个单词时，badness为500
            count[i] = 1;
            space[i] = 0;

            for (int k=2; k<=(n-i) && (curlen+length[i+k-1]+1)<=L; k++) // 枚举所有可能与word[i]在同一行的单词
            {
                curlen += (length[i+k-1]+1); // 当前行单词总长度--包括各单词间必须的1个空格

                int space_num = L - curlen; // 剩余用来分配的空格
                
                // 剩余空格的最优分配方式
                int bestbad = square(space_num/(k-1))*(k-1) + (2*(space_num/(k-1)) + 1)*(space_num%(k-1));

                // 最优子问题的解组成原问题的最优解
                if (f[i+k]+bestbad <= f[i]) // 塞尽可能多的单词，这里一定要是<=，否则会出现PE
                {
                    f[i] = f[i+k]+bestbad; // 更新最优解
                    count[i] = k;
                    space[i] = space_num;
                }
            }
        }

        print(0);
    }
}

int main()
{
    char line[N_MAX];
    while (NULL!=gets(line) && EOF!=sscanf(line, "%d", &L))
    {
        if (L == 0) break;

        n = 0;

        while (gets(line)) // 读入一行
        {
            if (line[0]<33 || 126<line[0]) // 判断空行，这里采用并未line[0]=='\0'判断空行，因为windows下的回车是两个字符
                break;
            
            int pos=0; int t=0;
            while (EOF != sscanf(&line[pos], "%s%n", words[n], &t)) // 格式符\n表示本次读过的字节数
            {
                length[n] = strlen(words[n]); // 记录各单词的长度
                ++n;

                pos += t; // 当前处理都得字符位置
                t = 0;
            }
        }
        
        format_text(); // 格式化文本，并输出

        printf("\n"); // 打印空行
    }
    
    return 0;
}

另外，值得注意的两组数据:


25
x x x x x  xxxxxxxxxxxxxx
x            xxxxxxxxxxxx
xxxxxxxxxxx             x
xxxxxxxxxxxxxx x x x x  x

5
La la la

结果:

x x x x x  xxxxxxxxxxxxxx
x            xxxxxxxxxxxx
xxxxxxxxxxx             x
xxxxxxxxxxxxxx x x x x  x

La la
la

• Re:终于AC了。 (95) sheeper 2013-02-28 23:06:04