#45912: 解題思路


henry.rem.rem@gmail.com (*ฅ́˘ฅ̀*)

學校 : 臺北市立松山高級中學
編號 : 278368
來源 : [1.161.41.35]
最後登入時間 :
2025-05-05 21:10:22
f608. 4. 飛黃騰達 -- 2021年1月APCS | From: [1.161.43.97] | 發表日期 : 2025-04-27 23:59

解題思路:

觀察題目,我們需要找出某種依照 x 、 y 遞增的序列,

但不需要找出序列本身,只需要知道其長度即可。

當想到遞增子序列、求長度後,很容易發現可以利用 LIS 實作。

LIS 就是所謂的最長遞增子序列 (Longest Increasing Subsequence) 

其最高效的一種解法,是利用二分搜,在迭代過程中,逐步選取並汰換已選擇元素,

令所選的子序列保持在最適合遞增的狀態。

這種演算法無法得知真正的 LIS 本身,僅能得知長度。

實作策略:

由於測資給予的座標點並未經過排序,

若我們直接對 x 或 y 單獨做 LIS ,有可能選到回頭的路徑,

也就是可能會確保了 x 的遞增,卻選到了 y 減少的座標。

為此,我們只需要先針對 x 或 y 做好排序,

再對另一者做 LIS ,即可求出答案。

範例解法

 
ZeroJudge Forum