IOI 2002 Batch Scheduling

傳說中的凸完全單調性優化

要倒著做的
dp[i] = 處理 job i 到 job N 的 minimum cost

O(N²) 的做法是 dp[i] = min{dp[k] + (S+T_i+T_i+1+…+ T_k-1) * (F_i+F_i+1+…+F_N) | i < k < N+1}
(即是後面的 job 的 factor 在前面計)


優化到O(N) [照著contest report打]

在compute dp[i] 時, 例如有2個決策 k 和 l (k < l)
即 dp[i] = dp[k] + ... 還是 dp[i] = dp[l] + ...

k 不差於 l 的條件是

dp[l] + (S+T_i+T_i+1+…+ T_l-1) * (F_i+F_i+1+…+F_N) ≥ dp[k] + (S+T_i+T_i+1+…+ T_k-1) * (F_i+F_i+1+…+F_N)
dp[l] - dp[k] + (T_k+T_k+1+…+ T_l-1)*(F_i+F_i+1+…+F_N) ≥ 0
(dp[k] - dp[l]) / (T_k+T_k+1+…+ T_l-1) ≤ (F_i+F_i+1+…+F_N)

設 g(k,l) = (dp[k] - dp[l]) / (T_k+T_k+1+…+ T_l-1) ; f(i) =  (F_i+F_i+1+…+F_N)

會得出2個特性

Property 1: 如果 g(k,l) ≤ f(i) , 咁對 dp[i] 黎講, k 比 l 更好
Property 2: 如果 g(j,k) ≤ g(k,l) , 咁對於 dp[i] 黎講, j 比 k 好 或 l 比 k 好


property 2 implies 對於 g(j,k) ≤ g(k,l) , 計 dp[i] 的時侯可以不用試 k 這個 choice

整個 algorithm 就係由 dp[N] 做到 dp[1]
maintain 住一條 deque Q, 滿足

1. q[1] > q[2] > q[3] ... > q[r]
2. g(q[r],q[r-1]) > g(q[r-1],q[r-2]) > ... > g(q[2],q[1])


計 dp[i] 時, 由 property 1 得知如果 f(i) ≥ g(q[2],q[1]) 咁 q[2] 比 q[1] 好
由於 f 是 increasing 的 (因為倒著做), 所以知道 q[1] 之後都唔會再有用, 可以 pop 走
所以可以不斷 pop queue head 直至 g(q[2],q[1]) > f(i)


現在有 g(q[r],q[r-1]) > g(q[r-1],q[r-2]) > ... > g(q[2],q[1]) > f(i)
由 property 1 的相反得知.. 現在 q[1] 對 i 是最 optimal 的

就能計算出 dp[i] 了

下一步就是要把 i push 入 Q
方法是由尾開始 pop 走加左 i 落去會唔符合 g(q[i],q[r]) > g(q[r],q[r-1]) 的點 (類似做 convex hull)