题意：有n根木棍，三根可能能够构成三角形，选出最多的三角形，问最大面积
分析：看到这个数据范围应该想到状压DP，这次我想到了。0010101的状态中，1表示第i根木棍选择，0表示没选，每一次三根木棍累加转移方程。虽说很简单，但是能自己独立敲出来还是很开心的，AC的快感！
/************************************************
* Author :Running_Time
* Created Time :2015/10/14 星期三 13:49:42
* File Name :I.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 13;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int a[N];
int l[4];
double dp[(1<<N)+10];
int n; bool judge(void) {
if ((l[1] + l[2] > l[3] && abs (l[1] - l[2]) < l[3]) &&
(l[1] + l[3] > l[2] && abs (l[1] - l[3]) < l[2]) &&
(l[3] + l[2] > l[1] && abs (l[3] - l[2]) < l[1])) return true;
else
return false;
} double area(void) {
double p = (l[1] + l[2] + l[3]) / 2.0;
return sqrt (p * (p - l[1]) * (p - l[2]) * (p - l[3]));
} int main(void) {
while (scanf ("%d", &n) == 1) {
if (!n) break;
for (int i=0; i<n; ++i) {
scanf ("%d", &a[i]);
}
sort (a, a+n);
int m = (1 << n);
memset (dp, 0, sizeof (dp));
for (int r=0; r<m; ++r) {
int k = __builtin_popcount (r);
if (k % 3 != 0) continue;
for (int i=0; i<n; ++i) {
for (int j=i+1; j<n; ++j) {
for (int k=j+1; k<n; ++k) {
if ((r & (1 << i)) == 0 && (r & (1 << j)) == 0 && (r & (1 << k)) == 0) {
l[1] = a[i], l[2] = a[j], l[3] = a[k];
if (!judge ()) continue;
int v = r;
v |= (1 << i); v |= (1 << j); v |= (1 << k);
dp[v] = max (dp[v], dp[r] + area ());
}
}
}
}
} double ans = 0;
for (int i=0; i<m; ++i) {
int k = __builtin_popcount (i);
if (k % 3 != 0 || k < 3) continue;
ans = max (ans, dp[i]);
}
printf ("%.2f\n", ans);
} return 0;
}