[Uva 1106][DP][操作分治] Machine Works

原題連結
 這裡 是這題完整的想法以及支持在線的作法，特地再寫一篇是因為像操作分治一類轉離線後的作法不僅code量少，時間和空間上的表現也都很優秀。

[Uva 1106][DP] Machine Works

原題連結
這道題目真是我見過最坑爹的一道題......

[SPOJ APIO10A][DP] Commando

題目連結
最單純的想法是1D/1D的DP，但是顯然不夠快。
這時候看看SPOJ的tag上寫著Convex Hull，然後就可以無恥的去做凸包優化了。