POJ 1739 Tony's Tour

非常慘烈的AC..

題目是最最最基本的插頭 dp, 其實在隊中不是我負責的, 不過做做也無妨
由於只有 3⁹ 種狀態, 所以便不用 hash, 直接做
但是因為不用 hash, 所以不能用 4 進制做 bitwise, 每次我都要把狀態 decode/encode
寫好後便是無限 WA..

WA 到不行的時侯, 便上網找別人的 code, 再怒 gen test case fc 自己的 output
不過也找不到 bug, 很灰, 一度懷疑是 test data 有 > 8 的情況, 但放了飛彈又沒有
最後發現 decode 一個 invalid 的狀態時, 會 access stack[-ive], 但不知為甚麼這情況只在特定 test data 出現

現在是 5/8 個男人了..!

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 咁

POJ 2986 - A Triangle and a Circle

要搵一個三角形的一個圓形 intersection 的面積

做法: 對於三角形ABC 和圓C, union的面積 = [ABO ∩ C] + [BCO ∩ C] + [CAO ∩ C] (signed area)
而每一次計圓心三角形的 intersection 可分為4個case

另外, 使用 asin 和 acos 時, 應該 handle asin(1.00000..001) 的情況