Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-30SRM300台を練習していく part6

SRM 314 GrasslandFencer

|  SRM 314 GrasslandFencer - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 314 GrasslandFencer - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6467

簡単なbitDP。


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GrasslandFencer {

	public double tri(double a, double b, double c) {
		double p = (a + b + c) / 2.0d;
		return Math.sqrt(p*(p-a)*(p-b)*(p-c));
	}

	public double maximalFencedArea(int[] fences) {
		int len = fences.length;
		if (len <= 2) {
			return 0.0;
		}

		java.util.Arrays.sort(fences);
		double dp[] = new double[1<<17];
		Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
		map.put(3, new HashSet<Integer>());
		for (int i = 0 ; i < len ; i++) {
			for (int j = i + 1 ; j < len ; j++) {
				for (int k = len - 1 ; k >= j + 1 ; k--) {
					if (fences[i] + fences[j] <= fences[k]) {
						continue;
					}
					int dpidx = 0;
					dpidx = dpidx | (1 << i);
					dpidx = dpidx | (1 << j);
					dpidx = dpidx | (1 << k);
					dp[dpidx] = tri(fences[i], fences[j], fences[k]);
					map.get(3).add(dpidx);
				}
			}
		}

		double maxres = 0.0d;
		for (int i = 6 ; i <= len ; i += 3) {
			map.put(i, new HashSet<Integer>());
			Set<Integer> ax = map.get(3);
			Set<Integer> bx = map.get(i - 3);
			for (int dpidx_a : ax) {
				for (int dpidx_b : bx) {
					if (Integer.bitCount((dpidx_a | dpidx_b)) == i) {
						int newdpidx = dpidx_a | dpidx_b;
						dp[newdpidx] = Math.max(dp[newdpidx], dp[dpidx_a] + dp[dpidx_b]);
						map.get(i).add(newdpidx);
					}
				}
			}
		}
		for (int i = 0 ; i < (1<<17L) ; i++) {
			maxres = Math.max(maxres, dp[i]);
		}
		return maxres;
	}
}