Ta có thể sử dụng quy hoạch động để giải bài này. Gọi ~dp(l, r)~ là số điểm lớn nhất nếu chỉ tính đoạn con liên tiếp từ ~l~ đến ~r~.

Với mỗi đoạn, ta cần chọn vị trí ~i~ nào đó làm số lớn nhất. Khi chọn được ~i~, đáp án sẽ tối ưu khi ~-C_{i, j} + V_{i, j} \cdot q(l, r, i) + dp(l, i - 1) + dp(i + 1, r)~ là lớn nhất, với ~q(l, r, i)~ là số lượng truy vấn trong đoạn ~[l, r]~ có chứa ~i~. Ta có thể tính được trước mảng ~q~ bằng prefix-sum 2D và giá trị ~-C_{i, j} + V_{i, j} \cdot q(l, r, i)~ tối ưu bằng quy hoạch động bao lồi.

Với cách tính trên, ~A_i~ sẽ luôn là số lớn nhất trong đoạn ~[l, r]~. Ta có thể chứng minh bằng phản chứng (Gợi ý: giả sử tồn tại ~A_x \gt A_i~ với ~x \in [l, r]~ và ~x \ne i~ ~\rightarrow \dots \rightarrow~ số điểm tính được sẽ lớn hơn ~dp(l, r)~ ~\rightarrow~ mâu thuẫn).

Độ phức tạp: ~O(N ^ 3 \cdot logK)~.