hdu 5135 狀態壓縮dp

hdu 5135 狀態壓縮dp

題意是給出最對12條邊你 問最大可組成三角形面積是多大 （可有多個三角形） 典型的狀態壓縮 （最多12條邊）

思路：
先暴力枚舉所有可能三角形的面積 然後再根據狀態壓縮來做 最多可組成n/3個三角形 對每個三角形都記錄三邊或（運算） 和面積 然後判斷進行合並 （根據且運算） 就行了

#include
#include
#include
#include
using namespace std;

double dp[1<<14];
double max(double a,double b)
{
    return a>b?a:b;
}
struct node
{
    int pp;
    double area;
}cont[1<<14];
int main()
{
    int n,i,j,k;
    int num[15];
    double S;
    while(~scanf("%d",&n),n)
    {
        for(i=1;i<=n;i++)
        scanf("%d",&num[i]);
        memset(dp,0,sizeof(dp));
        int t=0;
        S=0;
        for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        {
            for(k=j+1;k<=n;k++)
            {
                if(num[i]+num[j]>num[k]&&num[i]+num[k]>num[j]&&num[j]+num[k]>num[i])
                {
                    double p=1.0*(num[i]+num[j]+num[k])/2;
                    t++;
                    double s=sqrt(p*(p-num[i])*(p-num[j])*(p-num[k]));
                    cont[t].pp=(1<<i)|(1<<j)|(1<<k);
                    dp[(1<<i)|(1<<j)|(1<<k)]=cont[t].area=s;
                }
            }
        }
        for(i=1;i<(1<<(n+1));i++)
        {
            for(j=1;j<=t;j++)
            {
                if((i&cont[j].pp)==0)
                {
                    dp[i|cont[j].pp]=max(dp[i|cont[j].pp],dp[i]+cont[j].area);
                    if(dp[i|cont[j].pp]>S) S=dp[i|cont[j].pp];
                }
            }
        }
        printf("%.2lf\n",S);
    }
    return 0;
}