poj1093

题意：给出一个句子和要求整理后每行包含的字符数，要求将其整理为一种总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 ;

}