HDU 1421 搬寢室：動態規劃（排序後相鄰配對）

問題描述

有 n 件物品（重量 w_i），需選 2k 件搬運，每次搬兩件（左手一件、右手一件），疲勞度 = 兩件重量差的平方。求最小總疲勞度。2k ≤ n < 2000，重量 < 2^15。

核心觀察

排序後，最優配對必然是相鄰物品配對。證明：若存在交叉配對，交換後差值平方和不增（由凸性可證）。

動態規劃

• 排序重量數組 a[1..n] 遞增。
• dp[i][j]：前 i 件物品中選 j 對的最小疲勞度。
• 轉移：
  • 不選第 i 件：dp[i][j] = dp[i-1][j]
  • 選第 i 件（必與 i-1 配對）：dp[i][j] = min(dp[i][j], dp[i-2][j-1] + (a[i]-a[i-1])^2)
• 初始：dp[0][0] = 0，其餘 INF。
• 答案：dp[n][k]。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const long long INF = 0x3f3f3f3f3f3f3f3f;
long long dp[MAXN][MAXN/2];
int a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    while (cin >> n >> k) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        sort(a+1, a+n+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) dp[i][0] = 0;
        for (int j = 1; j <= k; ++j) {
            for (int i = 2*j; i <= n; ++i) {
                dp[i][j] = dp[i-1][j];
                long long cost = 1LL * (a[i] - a[i-1]) * (a[i] - a[i-1]);
                dp[i][j] = min(dp[i][j], dp[i-2][j-1] + cost);
            }
        }
        cout << dp[n][k] << '\n';
    }
    return 0;
}

複雜度

時間 O(n·k) ≤ 2000×1000 = 2×10⁶，空間 O(n·k) ≈ 2×10⁶ × 8 bytes ≈ 16 MB，完全符合限制。

關鍵點

1. 排序後相鄰配對最優（交換論證）。
2. DP 狀態定義清晰，轉移考慮「選/不選」當前物品。
3. long long 防溢出（差值平方最大 (2^15)^2 ≈ 10^9，k 最大 1000，總和 ≤ 10^12）。