這是問題描述：
The Amazing Circus 有 K 位雜技演員，他們通過在彼此的肩膀上跳躍來表演偉大的人塔。馬戲團的導演想要建造盡可能高的塔，以進入吉尼斯紀錄并吸引更多顧客。
每個雜技演員 i 有體重 W[i] 和力量 S[i]。雜技演員可以背著一堆雜技演員，總重量在 S[i] 以內。這應該包括 W[i]，它自己的權重，所以假設 S[i]≥W[i] 總是。
回傳驚人馬戲團可以建造的最高人塔的高度。
約束：
3 <= K <= 5000
1 <= 重量 <= 容量 <= 10^6。
所以對于這個問題，一開始我覺得這個問題有點類似于其他貪心演算法問題。但是當我查看約束時，似乎約束相對較大，因此蠻力或窮舉搜索效果不佳。關于如何解決這個問題的任何想法？
uj5u.com熱心網友回復：
這是一個帶有O(n^2)搜索空間的解決方案（n = K，雜技演員的總數）。讓我們f(i, h)代表最輕的塔的重量，h直到i第一個雜技演員，雜技演員按strength升序排列。然后：
f(i, h) = min(
f(i - 1, h),
weight(i) f(i - 1, h - 1)
if strength(i) ≥ weight(i) f(i - 1, h - 1) else Infinity
)
解釋排序技巧，改編自COMP3121/9101/3821/9801 講義；更多關于動態規劃（DP）；LiC：亞歷克斯·伊格尼亞托維奇；計算機科學與工程學院；新南威爾士大學；澳大利亞悉尼：
我們想證明我們可以通過strength升序重新排列任何合法的塔。為此，我們需要證明任何連續的對
(1) strength(a_i 1) < strength(a_i)
可以合法地交換，從那時起我們可以應用冒泡排序。換句話說，那
(2) (Sum j=1...i-1 of weight(a_j)) weight(a_i 1) weight(a_i) ≤ strength(a_i)
原始的、合法的塔有
(3) (Sum j=1...i?1 of weight(a_j)) weight(a_i) weight(a_i 1) ≤ strength(a_i 1)
將右邊的（1）代入，將左邊的最后兩項換掉：
(Sum j=1...i?1 of weight(a_j)) weight(a_i 1) weight(a_i) ≤ strength(a_i)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313564.html
標籤：算法