題意: 有一群大象，給每隻大象的體重 W 與智商 S，要你找出最大的子集合，滿足子集合 { a1, a2, a3, ..., an }中每隻大象滿足 W[ai] < W[ai+1] 且 S[ai] > S[ai+1]。
解法: LIS的變形，先將大象以體重排序，接著用LIS的方法再稍改即可。
(為求方便，加入第 0 隻大象，此大象體重最小，智商最大)
遞迴式: dp[i] 代表以第 i 隻大象為尾的最長大象序列的長度
dp[i] =
{ 0, if i = 0
{ max{ dp[j] }+1, if W[j] < W[i] & S[j] > S[i] & 0 <= j < i
TAG: DP, LIS
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽