描述小 G 是一个出色的诗人经常作诗自娱自乐。但是他一直被一件事情所困扰那就是诗的排版问题。一首诗包含了若干个句子对于一些连续的短句可以将它们用空格隔开并放在一行中注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度行的长度为一行中符号的总个数他希望排版后每行的长度都和行标准长度相差不远。显然排版时不应改变原有的句子顺序并且小 G 不允许把一个句子分在两行或者更多的行内。在

#include #include #include using namespace std;

long long calc_discrepancy(vector& lengths, int standard_length, int p) { int n = lengths.size(); vector dp(n+1, LLONG_MAX); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = i-1; j >= 0; j--) { int length = 0; for (int k = j; k < i; k++) { length += lengths[k]; } int diff = abs(length - standard_length); dp[i] = min(dp[i], dp[j] + pow(diff, p)); } } return dp[n]; }

void arrange_poem(vector& lengths, int standard_length) { int n = lengths.size(); vector<vector> lines; vector line; int line_length = 0; for (int i = 0; i < n; i++) { if (line_length + lengths[i] <= standard_length) { line.push_back(lengths[i]); line_length += lengths[i]; } else { lines.push_back(line); line.clear(); line.push_back(lengths[i]); line_length = lengths[i]; } } lines.push_back(line);

for (int i = 0; i < lines.size(); i++) {
    for (int j = 0; j < lines[i].size(); j++) {
        cout << lines[i][j] << " ";
    }
    cout << endl;
}

}

int main() { int T; cin >> T; for (int t = 0; t < T; t++) { int N, L, P; cin >> N >> L >> P; vector lengths(N); for (int i = 0; i < N; i++) { string sentence; cin >> sentence; lengths[i] = sentence.length(); } long long discrepancy = calc_discrepancy(lengths, L, P); if (discrepancy <= pow(10, 18)) { cout << discrepancy << endl; arrange_poem(lengths, L); } else { cout << "Too hard to arrange" << endl; } for (int i = 0; i < 20; i++) { cout << "-"; } cout << endl; } return 0;