算法标签

动态规划

题解

对于每个单词 i，尝试将其与后续的单词组合成一行，计算不同组合下的 “不美观度”。若从第 i 个单词到第 j 个单词排版在一行，“不美观度” 为 Cal(i, j)，则状态转移方程为：(b[i] = min_{j = i + 1}^{m} { b[j] + Cal(i, j) })

#include <iostream>
#include <cstring>
#define MAXN 10010
using namespace std;

char word[MAXN][82];
int a[MAXN], aft[MAXN], b[MAXN], m, n;

void Blank(int k) {
    for (; k--;)
        cout << ' ';
}

int Cal(int i, int j) {
    int g, t, k, ret;
    if (j == i + 1)
        return 500;
    t = n - (a[i] - a[j]);
    k = j - i - 1;
    g = t / k;
    ret = k * g * g + (t % k) * (2 * g + 1);
    return ret;
}

void Input() {
    int i, j, k;
    string line;
    k = 0;
    // 消耗可能的多余换行符
    cin.ignore();
    while (getline(cin, line) && !line.empty()) {
        i = 0;
        while (i < line.length()) {
            while (i < line.length() && line[i] == ' ') i++;
            if (i == line.length()) break;
            j = 0;
            while (i < line.length() && line[i] != ' ') {
                word[k][j] = line[i];
                i++;
                j++;
            }
            word[k][j] = '\0';
            k++;
        }
    }
    m = k;
    n++;
    a[m] = 0;
    for (i = m - 1; i >= 0; i--)
        a[i] = (int)strlen(word[i]) + 1 + a[i + 1];
}

void Solve() {
    int i, j, k;
    b[m] = 0;
    for (i = m - 1; i >= 0; i--) {
        b[i] = b[i + 1] + 500;
        aft[i] = i + 1;
        for (j = i + 2; j <= m && a[i] - a[j] <= n; j++) {
            k = Cal(i, j);
            if (b[i] > b[j] + k || (b[i] == b[j] + k && Cal(i, j) < Cal(i, aft[i])))
                b[i] = b[j] + k, aft[i] = j;
        }
    }
}

void Print() {
    int k, t, g, d, i, j;
    for (i = 0; i < m; i = j) {
        j = aft[i];
        if (j == i + 1) {
            cout << word[i] << endl;
        } else {
            t = n - (a[i] - a[j]);
            k = j - i - 1;
            g = t / k;
            d = k - (t % k);
            for (; d--; i++) {
                cout << word[i] << ' ';
                Blank(g);
            }
            for (; i + 1 < j; i++) {
                cout << word[i] << "  ";
                Blank(g);
            }
            cout << word[i] << endl;
        }
    }
}

int main() {
    while (cin >> n && n) {
        Input();
        Solve();
        Print();
        cout << endl;
    }
    return 0;
}