hdu5135 Little Zu Chongzhi's Triangles --状压dp

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=5135​​

题意：n根木棒，组成若干三角形，求最大面积和。

分析：把所有木棒升序排序，可以组成三角形所有的的组合利用位运算压缩放进vector里。然后一个个找就行。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

int n;
int v[13];
double dp[1 << 12];
vector<int> vec;

double getArea(int a, int b, int c)
{
  if (a + b <= c)
    return 0.0;
  double p = 0.5*(a + b + c);//注意是double
  return sqrt(p*(p - a)*(p - b)*(p - c));
}

int main()
{
  while (scanf("%d", &n) && n)
  {
    vec.clear();
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; i++)
      scanf("%d", &v[i]);

    sort(v, v + n);//注意排序

    for (int i = 0; i < n; i++)
    {
      for (int j = i + 1; j < n; j++)
      {
        for (int k = j + 1; k < n; k++)
        {
          int index = (1 << i) | (1 << j) | (1 << k);
          dp[index] = getArea(v[i], v[j], v[k]);
          if (v[i] + v[j]>v[k])
            vec.push_back(index);
        }
      }
    }

    for (int i = 0; i < (1 << n); i++)
    {
      for (int j = 0; j < vec.size(); j++)
      {
        if (i&vec[j])
          continue;
        dp[i | vec[j]] = max(dp[i | vec[j]], dp[i] + dp[vec[j]]);
      }
    }

    printf("%.2lf\n", dp[(1 << n) - 1]);
  }
  return 0;
}