🔴 Hard

劃分型 DP + 斜率優化（凸包優化）。將轉移方程化為內積形式，用下凸包維護候選點，二分查詢最優決策；再利用查詢向量的單調性，用單調隊列取代二分，達到 O(kn)。