AOJ1222 Telescope

問題リンク Telescope

• 概要

半径1の円周上の点がN個与えられる。これらの点を使ってM角形を作った時の最大面積を答えよ。
3 <= M <= N <= 40

• 解法

いくら考えても分からなかったのでプログラムプロムナードを参考にしました。
メモ化再帰で解きます。
始点sを決めている前提で、dp[j][k]を、j個目の点に点kを採用したときの最大面積とします。
dp[j][k]はk+1〜n-1の中から点iを1つを選び、(area(k, i)+dp[j+1][i])が最大となるものを採用すれば求まります。
当初は、M角形に点を1個足してM+1角形を得ようという方針で行こうとしていたのですが、面積最大M+1角形は面積最大M角形を含むとは限らず、そもそも動的計画法もといメモ化を適用できないことをやっていました。

• ソース

import java.util.Arrays;
import java.util.Scanner;
import static java.lang.Math.*;

//Telescope
public class AOJ1222 {

	int n, m, INF = 1<<29, s;
	double[] p;
	double[][] dp;
	
	double area(int i, int j){
		return sin((p[j]-p[i])*2*PI)/2;
	}
	
	double get(int j, int k){
		if(j==m-1)return area(k, s);
		if(dp[j][k]!=-INF)return dp[j][k];
		double max = -INF;
		for(int i=k+1;i<n;i++)max=max(max, area(k, i)+get(j+1, i));
		return dp[j][k] = max;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt(); m = sc.nextInt();
			if((n|m)==0)break;
			p = new double[n];
			for(int i=0;i<n;i++)p[i] = sc.nextDouble();
			double max = 0;
			for(int i=0;i<n;i++){
				dp = new double[m][n];
				for(double[]a:dp)Arrays.fill(a, -INF);
				s = i;
				max = max(max, get(0, s));
			}
			System.out.printf("%.6f\n", max);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1222().run();
	}
}