首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

HDU 1421 搬寢室:線性 DP + 貪心預處理求最小疲勞度

     編輯:關於C++

題目大意

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 個元素,相鄰配對,最小化差值平方和。

DP 定義與轉移

排序後預處理 diff[i] = (a[i+1]-a[i])² (1≤i dp[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,完全可行。

參考代碼(C++)

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved