發表新討論
#24568: upper bound


wallacechu0409@gmail.com (Wallace Chu)

f608. 4. 飛黃騰達 -- 2021年1月 APCS | From: [58.114.189.14] | 發表日期: 2021-03-05 22:23

和第三題不同的是，要用upper bound 去寫動態規劃(第三題是lower bound )

#25295: Re:upper bound


ptyc4076@gmail.com (Bernie)

f608. 4. 飛黃騰達 -- 2021年1月 APCS | From: [114.40.169.51] | 發表日期: 2021-05-07 05:06

和第三題不同的是，要用upper bound 去寫動態規劃(第三題是lower bound )


請問為什麼不能用lower bound呢

我用lower bound卡在30% 找不到錯在哪

#25296: Re:upper bound


ptyc4076@gmail.com (Bernie)

f608. 4. 飛黃騰達 -- 2021年1月 APCS | From: [114.40.169.51] | 發表日期: 2021-05-07 05:11

和第三題不同的是，要用upper bound 去寫動態規劃(第三題是lower bound )


請問為什麼不能用lower bound呢

我用lower bound卡在30% 找不到錯在哪


我想到了 因為我已經對x軸進行排序，所以若遇到y軸相同的座標，前面座標的x軸一定小於後面座標的x軸，所以是可以加入LIS的

所以才需要用upper bound 

#33425: Re: upper bound


winch (安可)

f608. 4. 飛黃騰達 -- 2021年1月 APCS | From: [163.21.229.5] | 發表日期: 2023-01-05 14:46

和第三題不同的是，要用upper bound 去寫動態規劃(第三題是lower bound )


請問為什麼不能用lower bound呢

我用lower bound卡在30% 找不到錯在哪


我想到了 因為我已經對x軸進行排序，所以若遇到y軸相同的座標，前面座標的x軸一定小於後面座標的x軸，所以是可以加入LIS的

所以才需要用upper bound 

用upper_bound並不是你說的對x軸做字典序排序產生問題，因為假如LIS={1,2,3,5}    當 val=2 要加入時 會變成  LIS={1,2,2,5} (因為LIS並不是嚴格遞增，但3為何還換成2，因為2比3更有潛力產生非嚴格遞增序列) 用lower_bound就做不到。但lower_bound是適用產生嚴格遞增LIS。

參考

https://web.ntnu.edu.tw/~algo/Subsequence.html#5 

假如用lower_bound

ZeroJudge Forum