题意分析

题目要求将一段文本（由多个单词组成）打印到多行中，每行最多包含 M 个字符。单词之间需要用恰好一个空格分隔。如果某行的实际字符数（单词总长度 + 空格数）小于 M，则需要计算惩罚值 (M - 实际字符数)^2。目标是找到一种换行方式，使得总惩罚值最小。

解题思路

1. 动态规划（DP）

   • 定义 dp[i][s] 表示前 i 个单词，当前行剩余 s 个字符空间时的最小惩罚值。
   • 状态转移：
     • 情况1：将第 i 个单词放在新的一行，此时惩罚值增加 (M - L[i])^2。
     • 情况2：将第 i 个单词接在前一行后面（如果剩余空间足够），此时惩罚值更新为 原惩罚值 - 上一行惩罚值 + 新惩罚值。
   • 最终答案：min(dp[n][s])，其中 s 是任意可能的剩余空间。

2. 关键优化

   • 预处理 dp[i-1][s] 的最小值，避免重复计算。
   • 确保 s 的范围在 [0, M] 之间，防止越界。

代码示例

#include <iostream>
#include <cstring> // for memset
using namespace std;
#define INT_MAX 2e9
const int maxM = 108; // 每行最大字符数
const int maxN = 10004; // 最大单词数

int dp[maxN + 10][maxM + 10]; // dp[i][s]：前i个单词，当前行剩余s字符时的最小惩罚
int L[maxN]; // 存储每个单词的长度

int main() {
    int cases;
    scanf("%d", &cases); // 测试用例数
    while (cases--) {
        int m, n, s;
        scanf("%d%d", &m, &n); // m: 每行最大字符数，n: 单词数
        for (int i = 1; i <= n; ++i)
            scanf("%d", &L[i]); // 输入每个单词的长度

              // 手动初始化 dp 数组为极大值（替代 memset）
        for (int i = 0; i <= maxN; ++i)
            for (int j = 0; j <= maxM; ++j)
                dp[i][j] = INT_MAX; // 或 0x7f7f7f7f
        dp[0][m] = 0; // 初始状态：0个单词，剩余m字符，惩罚值0

        for (int i = 1; i <= n; ++i) {
            // 情况1：将第i个单词放在新的一行
            int min_prev = dp[maxN][maxM]; // 初始极大值
            for (s = m; s >= 0; --s)
                min_prev = min(min_prev, dp[i - 1][s]); // 找到前i-1个单词的最小惩罚
            dp[i][L[i]] = min_prev + (m - L[i]) * (m - L[i]); // 新行惩罚

            // 情况2：将第i个单词接在前一行后面（如果剩余空间足够）
            for (s = L[i] + 2; s <= m; ++s) { // s=L[i]+1（单词长度+1个空格）
                int prev_space = s - L[i] - 1; // 前一行剩余空间
                if (dp[i - 1][prev_space] == dp[maxN][maxM])
                    continue; // 无效状态，跳过
                // 更新惩罚值：减去上一行惩罚，加上新惩罚
                int new_penalty = dp[i - 1][prev_space] - (m - prev_space) * (m - prev_space) + (m - s) * (m - s);
                dp[i][s] = new_penalty;
            }
        }

        // 最终答案：遍历所有可能的剩余空间s，取最小惩罚
        int ans = dp[0][maxM]; // 初始极大值
        for (s = 0; s <= m; ++s)
            ans = min(ans, dp[n][s]);
        printf("%d\n", ans);
    }
    return 0;
}

代码解释

1. 初始化

   • dp 数组初始化为极大值（0x7f），表示不可达状态。
   • dp[0][m] = 0 表示 0 个单词时，剩余 m 字符，惩罚值为 0。

2. 动态规划转移

   • 情况1（新行）：遍历前 i-1 个单词的所有可能剩余空间 s，找到最小惩罚值 min_prev，然后计算新行惩罚 (m - L[i])^2。
   • 情况2（接前行）：检查是否能将当前单词接在前一行末尾，并更新惩罚值。

3. 结果计算

   • 遍历 dp[n][s]（所有可能的剩余空间 s），取最小值作为答案。

复杂度分析

• 时间复杂度：O(n * m)，其中 n 是单词数，m 是每行最大字符数。
• 空间复杂度：O(n * m)，由 dp 数组决定。