BOJ 1139 - 울타리

BOJ 1139 - 울타리

완전탐색으론 불가능한 비트마스크 DP 문제이다.

사실 비트마스크 DP라고 하면 더 이상 설명할 것 없이 계속 삼각형들을 골라서 계산만 해주면 되기 때문에 쉽다.

int bcnt(ll x) { return __builtin_popcountll(x); }
int rz(ll x) { return __builtin_ctzll(x); }
int lz(ll x) { return __builtin_clzll(x); }
int msb(ll x) { return 63 - lz(x); }
double area(int a, int b, int c) {
   double p = (a + b + c) / 2.0;
   return sqrt(p * (p - a) * (p - b) * (p - c));
}
void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   sort(all(a));
   vector<double> dp(1 << n, -1);
   function<double(int)> fn = [&](int bit) -> double {
      if (n - bcnt(bit) < 3) return 0;
      double &ret = dp[bit];
      if (ret > -0.5) return ret;
      ret = 0;

      vi cand;
      for (int i = 0; i < n; i++) if (!(bit & (1 << i))) cand.pb(i);
      int c = sz(cand);
      for (int i = 0; i < c; i++) {
         for (int j = i + 1; j < c; j++) {
            for (int k = j + 1; k < c; k++) {
               if (a[cand[i]] + a[cand[j]] > a[cand[k]]) {
                  int mask = 1 << cand[i];
                  mask |= 1 << cand[j];
                  mask |= 1 << cand[k];
                  maxa(ret, fn(bit | mask) + area(a[cand[i]], a[cand[j]], a[cand[k]]));
               }
            }
         }
      }

      return ret;
   };
   cout << setprecision(15) << fixed << fn(0);
}