n 件物品(n<2000),重量已知。每次雙手各拿一件(共 2k 件,2k≤n),疲勞度為兩手重量差的平方。求挑選 2k 件並配對後的最小總疲勞度。
最優配對必然是將選中的 2k 件按重量排序後相鄰配對。證明:若存在交叉配對 (a,d) 和 (b,c) 且 a≤b≤c≤d,則 (d-a)²+(c-b)² ≥ (b-a)²+(d-c)²(展開後等價於 (d-c)(b-a) ≥ 0)。因此問題轉化為:排序後從中選 2k 個元素,相鄰配對,最小化差值平方和。
排序後預處理 diff[i] = (a[i+1]-a[i])² (1≤idp[i][j]:前 i 個差值(對應前 i+1 個物品)中選 j 對的最小疲勞度。
轉移:dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + diff[i])(不選第 i 個差值 / 選第 i 個差值,則 i-1 不能選)。
初始:dp[*][0]=0, dp[1][1]=diff[1], 其餘 INF。
答案:dp[n-1][k]。
時間 O(n k),空間 O(n k)(可優化至 O(k) 滾動數組)。n<2000, k≤n/2,完全可行。