I-Little Zu Chongzhi’s Triangles

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5135
这题贪心是错的，但是数据有点水，阔以过，但这组数据就不得行：
input：
5
51 13 40 92 45
0
output：
862.82

可以暴力写个dfs，但是我不会T_T，幸好彭老板会~
这题正解应该是状压dp，先弄出最初的三条边的价值，然后再进行状态转移：
这里枚举每个状态 <nobr aria&#45;hidden="true"> sta </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> s </mi> <mi> t </mi> <mi> a </mi> </math>： 假如 <nobr aria&#45;hidden="true"> sta </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mi> s </mi> <mi> t </mi> <mi> a </mi> </math> 和当前的可以组成三角形的状态没有重合的边，也就是说他们两个相 &是等于0 的那么他们两个组合起来的状态就阔以由这两个转移过来

#include"bits/stdc++.h"
using namespace std;
const int maxn=20;
int a[maxn];
double dp[1<<maxn];
double calc(double A,double B,double C)
{
    double P=(A+B+C)/2.0;
    double res=P*(P-A)*(P-B)*(P-C);
    if(res<0)return -1;
    else return sqrt(res);
}
int main()
{
    cout.setf(ios::fixed);
    int N;
    while(cin>>N&&N)
    {
        memset(dp,0,sizeof dp);
        vector<int>V;
        for(int i=0;i<N;i++)cin>>a[i];
        for(int i=0;i<N;i++)
        {
            for(int j=i+1;j<N;j++)
            {
                for(int k=j+1;k<N;k++)
                {
                    double tp=calc(a[i],a[j],a[k]);
                    if(tp<0)continue;
                    int sta=0;
                    sta=(1<<i)|(1<<j)|(1<<k);
                    dp[sta]=tp;
                    V.push_back(sta);
                }
            }
        }
        double ans=0;
        for(int sta=0;sta<(1<<N);sta++)
        {
            for(int i=0;i<V.size();i++)
            {
                int t=sta&V[i];
                if(t)continue;//Èç¹ûÓÐÖغϵı߾Ͳ»ÐÐ 
                int now=sta|V[i];//еÄ×éºÏ 
                dp[now]=max(dp[now],dp[sta]+dp[V[i]]);
                ans=max(ans,dp[now]);
            }
        }
        cout<<setprecision(2)<<ans<<endl;
    }
}