algorithm - 動的計画法の最適化、凸包

Question

コンテストで出題される問題があります。私はすでにこの問題を動的プログラミングとその複雑さで解決しましたが、O(n^2)より効率的な方法を探しています。動的プログラミングが凸包で最適化できることはすでに見ました。何か提案はありますか。アドバイスありがとう。

Answer 1

おそらく、動的プログラミングの凸包トリックについて言及しているでしょう: http://wcipeg.com/wiki/Convex_hull_trick

Answer 2

凸包アルゴリズムには、複雑さが異なるいくつかのアルゴリズムがリストされています。