[BAE/<JOON> 문제풀이] 1139. 울타리

https://www.acmicpc.net/problem/1139

1139번: 울타리

서론

N 이 10 초반 ~ 10 후반 인 문제는 대부분 비트마스크 문제였던 것 같다.

---

풀이

각각의 울타리 사용 여부를 비트에 대응시키고 아직 확인하지 않은 상태일 때만 검사를 진행하면 된다.

한번에 3개씩 묶어서 조작해야하니까 구현이 살짝 복잡하긴 하다.

---

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct pa {
	ll sum, cnt;
};
struct pos {
	int x, y, cnt;
};
int mvx[4] = { 0 ,1, 0, -1 };
int mvy[4] = { 1, 0, -1, 0 };
vector<short> arr; int n; vector<double> dp; double mx = 0;
double gets(double a, double b, double c) {
	vector<double> sl = { a, b, c };
	sort(sl.begin(), sl.end());
	if (sl[0] + sl[1] <= sl[2]) return -1;
	double p = (sl[0] + sl[1] + sl[2]) / 2;
	return sqrt(p * (p - sl[0]) * (p - sl[1]) * (p - sl[2]));
}
double getmx(int bm) {
	double& ret = dp[bm];
	if (ret > 0) return ret;
	vector<int> avlist;
	for (int i = 0; i < n; i++) {
		if ((bm & (1 << i)) == 0) {
			avlist.push_back(i);
		}
	}
	if (avlist.size() < 3) return ret = 0;
	int m = avlist.size();	
	for (int i = 0; i < m - 2; i++) {
		for (int j = i + 1; j < m - 1; j++) {
			for (int k = j + 1; k < m; k++) {
				int nbm = bm | (1 << avlist[i]) | (1 << avlist[j]) | (1 << avlist[k]);
				double s = gets(arr[avlist[i] + 1], arr[avlist[j] + 1], arr[avlist[k] + 1]);
				if (s == -1) continue;								
				double p = s + getmx(nbm);
				ret = p > ret ? p : ret;
			}
		}
	}
	return ret;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n; arr = vector<short>(n + 1); dp = vector<double>((1 << n) - 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}	
	printf("%.9lf", getmx(0));
	return 0;
}