#29368: 題解


becaido (Caido)

School : 臺北市立建國高級中學
ID : 83294
IP address : [60.248.156.9]
Last Login :
2024-05-16 19:51:00
f995. 疊疊杯子蛋糕 - Extreme -- Caido | From: [60.248.156.9] | Post Date : 2022-02-18 23:30

很容易看出這題是一題 $\color{black}{dp}\ $ 題,$\color{black}{dp}\ $ 式經過化簡與計算後,可以得到 $\color{black}{dp_i = MAX^{i-1}_{j=max(0,i-K)}(m_j\times x_i+k_j)+c_i}\ $

如果直接去做的話,時間複雜度是 $\color{black}{O(nk)}\ $,顯然不行。

如果想要快速得到如上面有斜率的 $\color{black}{dp}\ $ 值,可以用斜率優化,但是這題斜率不單調,查詢也不單調,無法使用 $\color{black}{O(n)}\ $ 的斜率優化,需要用到一種資料結構叫做「李超線段樹」,基本上就是在線段樹上的節點存直線,當值域很大時需要動態開點,每次可以插入直線或查詢插入直線裡 $\color{black}{mx+b}\ $ 的最大值。

在 f994 就是直接用一棵李超線段樹去維護就好了,空間複雜度 $\color{black}{O(n)}\ $,因為每次插入時至多多一個節點,時間複雜度則是 $\color{black}{O(nlogC)}\ $,$\color{black}{C}\ $ 為值域。

在這一題因為只能由前 $\color{black}{K}\ $ 個點轉移,所以或許有一種想法就是將編號 $\color{black}{0\sim n}\ $ 每 $\color{black}{M}\ $ 個分一段,總共有 $\color{black}{\frac{n}{M}}\ $ 段,每段用一個李超線段樹維護,代表此段的最大值,每次需要訪問 $\color{black}{\frac{K}{M}}\ $ 個李超線段樹,加上最多 $\color{black}{M}\ $ 個落單的節點,單次更新時間複雜度為 $\color{black}{O(\frac{K}{M}logC+M)}\ $,根據算幾不等式,$\color{black}{M=\sqrt{KlogC}}\ $ 時最佳。此作法空間複雜度為 $\color{black}{O(n)}\ $,時間複雜度為 $\color{black}{O(N\sqrt{KlogC})}\ $,但是還是會 $\color{blue}{TLE}\ $。

第三個做法就是把 $\color{black}{0\sim n}\ $ 分成很多個區間,可以想像成是一棵線段樹,每個線段樹存的是根節點的編號,對應到每個節點代表的李超線段樹,每次更新好 $\color{black}{dp}\ $ 值時也同時把這個編號的直線在之後可能會用到的區間插入,共 $\color{black}{logn}\ $ 個區間,每次要查詢極值時再找出此編號所在區間的李超線段樹的值,繼續向下在更下層的線段樹節點遞迴,並更新最大值。此作法空間複雜度 $\color{black}{O(nlogn)}\ $,時間複雜度 $\color{black}{O(nlognlogC)}\ $,即可 $\color{green}{AC}\ $ 此題。

如果有人有更好的想法,歡迎提出!

 
ZeroJudge Forum