很容易看出這題是一題 $\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}\ $ 此題。

如果有人有更好的想法，歡迎提出！