POJ 3709 K-Anonymous Sequence

斜率優化DP

重要的observation
1. If k->i is better than j->i and k > j, then for all r >= i, k->r is better than j->r
2. For all j < k, there exists i such that for all r >= i, k->r is better than j->r *

然後做 DP 時, maintain 住一條 queue, 乎合以下條件

1. 在當前的 i, q[x] 比 q[x+1] 好
2. q[y] 比 q[y-1] 好的時間 大於 q[y-1] 比 q[y-2] 好的時間

每次取計算 DP 值時, 先用條件(1) pop 走 queue 頭
再用條件(2) pop 走 queue 尾, 再把 i-m+1 push 進 queue 尾


* 有時 i 會是 +inf 或 -inf, 可以 handle 做 0 或者 n+1 咁