状压DP

Little Zu Chongzhi‘s Triangles

3
1 1 20
7
3 4 5 3 4 5 90
0

0.00
13.64

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn=30;

int n;
int a[maxn];
int ken[1<<14],kn;
double area[1<<14];
double dp[1<<14];

int main()
{
    while(scanf("%d",&n)!=EOF&&n)
    {
        memset(ken,0,sizeof(ken)); kn=0;
        memset(area,0,sizeof(area));
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            scanf("%d",a+i);
        }
        sort(a,a+n);
        /// mei ju san ge bian
        bool flag=false;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if(a[i]+a[j]>a[k]&&a[j]+a[k]>a[i]&&a[k]+a[i]>a[j])
                    {
                        flag=true;
                        double A=a[i],B=a[j],C=a[k];
                        double p=(A+B+C)/2.;
                        double s=sqrt(p*(p-A)*(p-B)*(p-C));
                        int id=(1<<i)|(1<<j)|(1<<k);
                        ken[kn]=id;
                        area[kn++]=s;
                    }
                }
            }
        }
        if(flag==false)
        {
            puts("0.00"); continue;
        }
        double ans=0.0;
        for(int i=0;i<(1<<n);i++)
        {
            for(int j=0;j<kn;j++)
            {
                if((i&(ken[j]))==0)
                {
                    int now=i|ken[j];
                    dp[now]=max(dp[now],dp[i]+area[j]);
                }
            }
            ans=max(dp[i],ans);
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}

HDOJ 5135 Little Zu Chongzhi's Triangles 状压DP

原文：http://blog.csdn.net/ck_boss/article/details/41720925