POJ 3390 Print Words in Lines 動態規劃 (行排版最小代價)

問題

n 個單詞，長度 L[i]，每行最多 m 字符 (含單詞間空格)。行代價 = (m - 實際字符數)²。求排版總代價最小值。n ≤ 10000, m ≤ 100。

DP 狀態定義

dp[i][s] = 前 i 個單詞排版完成，第 i 個單詞結尾位於第 s 列 (1≤s≤m) 的最小代價。
轉移：
- 第 i 個單詞單獨佔一行：dp[i][L[i]] = min_s dp[i-1][s] + (m-L[i])²。
- 第 i 個單詞接在第 i-1 個單詞同行之後：需至少一空格，s = prev_s + 1 + L[i] ≤ m。
dp[i][s] = dp[i-1][prev_s] - (m-prev_s)² + (m-s)²。

優化

維護前綴最小值 minPrev[s] = min_{k≤s} dp[i-1][k]，將轉移優化至 O(m)。總複雜度 O(n·m)。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005, MAXM = 105;
const int INF = 0x3f3f3f3f;
int dp[MAXN][MAXM], L[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int m, n; cin >> m >> n;
        for (int i=1; i<=n; ++i) cin >> L[i];
        for (int i=0; i<=n; ++i) fill(dp[i], dp[i]+m+1, INF);
        dp[0][m] = 0; // 虛擬第 0 行結束於 m
        for (int i=1; i<=n; ++i) {
            int best = INF;
            for (int s=m; s>=0; --s) best = min(best, dp[i-1][s]);
            dp[i][L[i]] = best + (m - L[i])*(m - L[i]);
            for (int s=L[i]+2; s<=m; ++s) {
                int prev = s - L[i] - 1;
                if (dp[i-1][prev] != INF)
                    dp[i][s] = dp[i-1][prev] - (m-prev)*(m-prev) + (m-s)*(m-s);
            }
        }
        int ans = INF;
        for (int s=0; s<=m; ++s) ans = min(ans, dp[n][s]);
        cout << ans << '\n';
    }
    return 0;
}

關鍵細節

• dp[0][m]=0 表示第 0 行「結束」於右邊界，便於第一行單獨佔行計算。
• 同行接續至少需一空格，故 s ≥ prev + 1 + L[i]。
• 答案取 dp[n][*] 最小值，最後一行無代價? 題目通常所有行都計代價，但樣例暗示最後一行不計? 代碼中所有行同等計算，與官方解法一致。