\(O(N^3)\) 時間です。

抽象化した問題で説明します。

どの \(3\) 点も同一直線上にないような \(N\) 点、ただし組 \((x,y)\) の辞書順に並んでいるとします。また、 \(i\lt j\) について重み \(W[i,j]\) が決まっています。

点の番号の長さ \(2\) 以上の狭義単調増加列 \((p _ 1,p _ 2,\ldots ,p _ n)\) のうち、 \(p _ 1 = s,p _ n = t\) を満たすものであって、対応する点を順に結んだ線が上に凸であるようなものすべてについて、

\[\prod_{k=1}^{n-1} W[p _ k,p _ {k+1}]\]

の値を足し合わせた値を \(Q[s,t]\) とおきます。

\(1\leq s \lt t \leq N\) となる整数 \(s,t\) すべてについて \(Q[s,t]\) の値を求めてください。

直接結ばれる点の組 \((p _ k,p _ {k+1})\) を辺と呼ぶことにします。辺からなる経路が上に凸であるためには、

• 経路をなす
• 傾きが単調減少である

を確認すれば必要十分なので、すべての辺を傾きでソートしたのちその順に経路を伸ばしてゆく DP を遷移させれば、 \(s\) ごとに \(O(N^2)\) 時間で計算できます。

\(\text{dp}[s][k]\) : \(s\) から \(k\) までの経路全体の重み和

辺のソートが \(O(N^2\log N)\) 時間、 DP が \(O(N^3)\) 時間、 Integer Convex Hull における \(W[i,j]\) の計算が \(O(N^3)\) 時間になるので、全体で \(O(N^3)\) 時間で計算できます。

実装例 (C++)