2000/Contest/つくば大会

Problem G : Telescope

問題概要

同一円周上にある与えられた n 点から m 点を選んで多角形を作る.これらの多角形のうちで面積が最大のものについて,その面積を出力する.

解法

S[m,i,j] なる表を作って順番に埋めていく(動的計画法).ここで S[m,i,j] は P[i]〜P[j] の中から m 個の点を選んで作った正多角形の面積.更新規則は次のとおり.[15 Dec 2004,泉]

S_{m+1,i,j} = \max_{i<k<j} S_{m,i,k} + \triangle P_iP_kP_j

議論・その他

  • fixed partition -- 2009-06-24 (水) 22:22:34

ファイルを添付する

filescope.out.txt 596件 [詳細] filescope.txt 622件 [詳細] fileizumi_G.cpp 658件 [詳細] filemikurube_G_TLE.c 590件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filescope.out.txt 596件 [詳細] filescope.txt 622件 [詳細] fileizumi_G.cpp 658件 [詳細] filemikurube_G_TLE.c 590件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:52 (2995d)