發表新討論
#24568: upper bound


wallacechu0409@gmail.com (Wallace Chu)

學校 : 國立臺灣師範大學附屬高級中學
編號 : 136430
來源 : [60.250.158.236]
最後登入時間 ：
2024-01-30 11:09:01
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)

學校 : 不指定學校
編號 : 136113
來源 : [61.227.115.152]
最後登入時間 ：
2024-10-29 22:20:38
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)

學校 : 不指定學校
編號 : 136113
來源 : [61.227.115.152]
最後登入時間 ：
2024-10-29 22:20:38
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 (安可)

學校 : 臺北市立忠孝國民中學
編號 : 8936
來源 : [163.21.229.5]
最後登入時間 ：
2023-05-05 14:06:35
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