AOJ 1222 : Telescope
問題リンク : Telescope | Aizu Online Judge
問題概要:
n個の点が円上に存在する
その内m個を選んだ時にできる多角形の面積の最大値を求めよ
解法:
動的計画法で解いた
dp[始点となる点][最後に使った点][点を選んだ回数]:=その時の最大面積 とした
for sp 0..n //始点 for cnt 2..m //点を選んだ回数 for lp sp+1..n //最後に選んだ点 for np lp+1..n //次に選ぶ点 dp[sp][np][cnt+1] = max(dp[sp][np][cnt+1], dp[sp][lp][cnt]+area(sp,lp,np) /* ここでarea(i,j,k)は三角形ijkの面積を返す */
コード:
typedef long double ld; int n,m; ld p[MAX]; ld area[MAX][MAX][MAX];//area[start point][last point][new point] := the area ld dp[MAX][MAX][MAX];//dp[start point][last point][the number] := maximum area double getArea(int i,int j) { assert(i < n && j < n); return sin((p[j]-p[i])*2*PI)/2.0;//S = (b*c*sinA)/2,in this case, b = c = 1 } void init_area() { rep(i,n)//start point { REP(j,i,n)//last point { REP(k,j,n)//new point { area[i][j][k] = getArea(i,j)+getArea(j,k)+getArea(k,i); } } } } int main() { while(cin >> n >> m,n|m) { rep(i,n)cin >> p[i]; init_area(); rep(i,MAX)rep(j,MAX)rep(k,MAX)dp[i][j][k] = -inf; rep(i,MAX)rep(j,MAX)dp[i][j][2] = 0; ld ans = -inf; rep(sp,n)//start point { REP(cnt,2,m)//the number of uses { REP(lp,sp+1,n)//last point { REP(np,lp+1,n)//new point { if(dp[sp][lp][cnt] == -inf)continue; dp[sp][np][cnt+1] = max(dp[sp][np][cnt+1], dp[sp][lp][cnt]+area[sp][lp][np]); if(cnt+1 <= m) ans = max(ans,dp[sp][np][cnt+1]); } } } } cout << setiosflags(ios::fixed) << setprecision(6) << ans << endl; } return 0; }