SRM 314 Div1 Medium GrasslandFencer

問題

フェンスが複数あり、それらの長さが与えられる。フェンスを使って三角形をいくつか作るとき、できた三角形の面積の総和を最大化せよ。ただし、複数のフェンスを使って1辺とすることや、1つのフェンスを複数に分割することはできない。

やりかた

bitDP。dp[S]:=（Sを使用したフェンスの集合とした時の面積の最大値）でDP。
関数内で、まだ使用していない3辺を指定して再帰をかける。

以下ソース。

double dp[1 << 20];

class GrasslandFencer {
public:
  int N;
  vector<int> f;
  double rec(int S){
    if((S + 1) >> N & 1) return 0.0;
    if(dp[S] >= 0.0) return dp[S];
    
    double tmp = 0.0;
    for(int i = 0; i < N; i++)
      for(int j = i + 1; j < N; j++)
	for(int k = j + 1; k < N; k++)
	  if(!(S >> i & 1) && !(S >> j & 1) && !(S >> k & 1)) //この3つは使用していない
	    tmp = max(tmp, 
		      area(f[i], f[j], f[k]) + rec(S | 1 << i | 1 << j | 1 << k));
    return dp[S] = max(dp[S], tmp);
  }
  double area(double a, double b, double c){
    if(a + b + c <= 2. * max(a, max(b, c))) return 0.0;
    double s = 0.5 * (a + b + c);
    return sqrt(s * (s - a) * (s - b) * (s - c));
  }
  double maximalFencedArea(vector <int> fences){
    N = fences.size();
    fill(dp, dp + (1 << 20), -1.0);
    f = fences;
    return rec(0);
  }
};