UVA 10271 筷子：線性 DP 從後向前優化空間

題目大意

有 N 根筷子 (長度非遞減)，需組成 K+8 套，每套 3 根：兩根短的長度盡量接近 (badness = (a-b)²)，一根長的無要求但必須最長。求最小總 badness。

約束：K ≤ 1000, 3K+24 ≤ N ≤ 5000。

關鍵觀察：從後向前 DP

因「長筷子無要求但必須最長」，若從小到大 DP，選長筷子時不知後面是否有更長的。從大到小 DP 可自然保證：當前考慮的筷子作為「長筷子」時，後面 (更小的) 只能作為短筷子。

狀態定義

dp[i][j]：考慮前 i 根筷子 (即最大的 i 根)，已組成 j 套的最小 badness。
筷子按長度遞減排序：a[1] ≥ a[2] ≥ ... ≥ a[N]。

轉移方程

• 不組套：第 i 根作為長筷子預留 (或丟棄) → dp[i][j] = dp[i-1][j]
• 組套：第 i 根作為長筷子，i-1 和 i-2 根作為短筷子 → dp[i][j] = min(dp[i][j], dp[i-3][j-1] + (a[i-1] - a[i-2])²)

注意：短筷子必須相鄰選取 (因已排序，相鄰差值最小)，且長筷子必須 ≥ 短筷子 (排序保證)。

完整代碼

#include <bits/stdc++.h>
using namespace std;

const long long INF = 4e18;
long long dp[5005][1005];
int a[5005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int K, N;
        cin >> K >> N;
        K += 8; // 總套數
        for (int i = N; i >= 1; --i) cin >> a[i]; // 逆序讀入，a[1] 最大

        // 初始化
        for (int i = 0; i <= N; ++i)
            for (int j = 0; j <= K; ++j)
                dp[i][j] = INF;
        dp[0][0] = 0;

        for (int i = 1; i <= N; ++i) {
            for (int j = 0; j <= K; ++j) {
                // 不用第 i 根
                dp[i][j] = dp[i-1][j];
                // 用第 i, i-1, i-2 組一套 (需 i≥3, j≥1)
                if (i >= 3 && j >= 1) {
                    long long cost = 1LL * (a[i-1] - a[i-2]) * (a[i-1] - a[i-2]);
                    dp[i][j] = min(dp[i][j], dp[i-3][j-1] + cost);
                }
            }
        }
        cout << dp[N][K] << '\n';
    }
    return 0;
}

空間優化：滾動數組

dp[i] 只依賴 dp[i-1] 和 dp[i-3]，可用 dp[4][K+1] 滾動：

long long dp[4][1005];
for (int i = 1; i <= N; ++i) {
    int cur = i % 4, pre1 = (i-1) % 4, pre3 = (i-3) % 4;
    for (int j = 0; j <= K; ++j) {
        dp[cur][j] = dp[pre1][j];
        if (i >= 3 && j >= 1) {
            long long cost = 1LL * (a[i-1] - a[i-2]) * (a[i-1] - a[i-2]);
            dp[cur][j] = min(dp[cur][j], dp[pre3][j-1] + cost);
        }
    }
}
cout << dp[N%4][K] << '\n';

複雜度分析

• 時間：O(N × K) = 5000 × 1008 ≈ 5×10⁶，極快
• 空間：O(N × K) = 5000 × 1008 × 8B ≈ 40MB，或滾動 O(K) ≈ 8KB

弱化版 NJUPT 1581 (雙筷子版)

無長筷子，只組 K+3 雙，最小化差值平方和。DP 更簡單：

dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + (a[i] - a[i-1])²);

總結

本題展示了逆序 DP處理「最大元素無約束但必須存在」的經典技巧：將無約束元素作為「預留/消耗」決策，從大到小處理時自然滿足大小關係。狀態設計簡潔，轉移直觀，是線性 DP 優秀範例。