は最大面積がk-gonが、私はトップコーダーのアリーナで練習問題を解決しようとしていたポイント

Question

のセットを与えられた見つけます領域D、kの集合を与えて< = n、nは固定値です。

は、D = C（D）

場合、N = 3の凸包をしましょう、私はこのような三角形は、それが頂点はC（D）のサブセットであるだと仮定することによって構築することができることを証明しています。 したがって、k = 3の解を考え出すのはかなり簡単でした。https://stackoverflow.com/a/1621913/4126652

ただし、n> 3の場合、これを行う方法はわかりません。ここで

は、私が試した方法です：

レッツ| C（D）| = Lすなわち凸包は

は、n>リチウムがk角形最大面積とは、凸包自体であろうことをかなり確信している場合、L角形である、すなわち、C（D）

N <場合私はk> 3のためにそれを証明することができませんでした、そして、私が解決するためのアルゴリズムを思い付くことができません。正しい仮定。

誰もがこれを手伝ってくれますか、私のアプローチは正しいですか？あなたは私がさらに進歩するのを助けることができますか？

Answer 1

私の頭を数時間壊した後、私は解決策を考え出しました。

それはダイナミックプログラミングの問題である：

DPが[M] [O] [R]最大面積を示すものとR角形ような出発頂点mは、終了頂点がOであること（頂点が取り込ま巡回順序）。

そして再発関係があろう：[O]

DP [M] [R] = MAX（DP [M] [N] [R-1] +領域（M、N、O））、 {n個すべてにわたる最大：M < N < O}

面積（mは、N、O）は、頂点mによって形成される三角形の面積であり、NおよびO