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

ファイルを添付する †

scope.out.txt

scope.txt

izumi_G.cpp

mikurube_G_TLE.c