程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 5135 狀態壓縮dp

hdu 5135 狀態壓縮dp

編輯:關於C++

題意是給出最對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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved