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

UVA 10271 Chopsticks:筷子組合最小總劣質度動態規劃

     編輯:C++ 入門

問題重述

有 N 根筷子(長度非遞減),需組成 K+8 套筷子。每套包含 3 根:兩根短筷 A≤B 和一根長筷 C (C≥B)。劣質度定義為 (A-B)²。求最小總劣質度。約束:K ≤ 1000, 3K+24 ≤ N ≤ 5000。

關鍵觀察

長筷 C 僅需滿足 C ≥ B,不影響劣質度。若從小到大 DP,選定 A,B 後難以保證後面有足夠的 C。**逆序思維**更優:將筷子按長度**從大到小排序**,先決定長筷 C,再選 A,B。這樣已處理的筷子都可作為 C,無可用性憂慮。

DP 狀態定義

`dp[i][j]`:從前 j 根筷子(最大的 j 根)中選出 i 套筷子的最小總劣質度。
轉移:第 j 根筷子不作為短筷 → `dp[i][j-1]`;第 j 根和第 j-1 根作為一套的短筷(需 j ≥ 3i) → `dp[i-1][j-2] + (a[j]-a[j-1])²`。取較小值。

優化與初始化

使用滾動數組優化空間至 O(N)。初始化 `dp[0][*]=0`,其餘為 INF。最終答案為 `min_{j≥3m} dp[m][j]`(m=K+8)。

正確性保證

逆序排序確保任意時刻「未使用」的筷子長度均 ≥ 當前考慮的筷子,故任兩根短筷後總能找到足夠的長筷。樣例驗證輸出 23 正確。

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