hdoj 5125 Little Zu Chongzhi's Triangles【状态压缩dp】

女爷i 2022-08-06 00:19 126阅读 0赞

题目：[hdoj 5125 Little Zu Chongzhi's Triangles][hdoj 5125 Little Zu Chongzhi_s Triangles]

题意：给出n个木棍的长度，然后问这些木棍所能组成三角形的最大面积。

分析：这个题目用状态压缩解，因为木棍的最大个数为12

我们枚举所有状态，用状态对应位的 0 和 1 表示这个木棍是否选择，然后如果某个状态选择的木棍是3的话，判断是否可以组成，可以的话dp【st】 = 三角形面积

然后大于三的，分解之后得出转移方程dp【st】 = max（dp【st】，dp【i】 + dp【st - i】） （i | （st - i）== st）

AC代码：

#include <stdio.h>
    #include <algorithm>
    #include <cstring>
    #include <iostream>
    #include <cmath>
    #include <vector>
    using namespace std;
    const int N = 15;
    
    bool Judge(double a,double b,double c)
    {
        if((a+b)>c && (a+c)>b && (b+c)>a)
            return true;
        return false;
    }
    double Solve(double a,double b,double c)
    {
        double p = (a+b+c)/2.0;  //zhuyi
        return sqrt(p*(p-a)*(p-b)*(p-c));
    }
    double a[N],dp[1<<N];
    vector<int> v;
    int main()
    {
        int n;
        while(~scanf("%d",&n) && n)
        {
            for(int i=0;i<n;i++)
            {
                scanf("%lf",&a[i]);
            }
            memset(dp,0,sizeof(dp));
            for(int st = 1 ;st < (1<<n); st++)
            {
                for(int i=0;i<n;i++)
                {
                    if(st&(1<<i))
                        v.push_back(i);
                }
                if(v.size()==3)
                {
                    if(Judge(a[v[0]],a[v[1]],a[v[2]]))
                        dp[st] = max(dp[st],Solve(a[v[0]],a[v[1]],a[v[2]]));
                }
                for(int i = 0;i<st;i++)
                {
                    if((i|(st-i))==st) //与的运算符优先级低
                        dp[st] = max(dp[st],dp[i]+dp[st-i]);
                }
                v.clear();
            }
            printf("%.2lf\n",dp[(1<<n)-1]);
        }
        return 0;
    }

[hdoj 5125 Little Zu Chongzhi_s Triangles]: http://acm.hdu.edu.cn/showproblem.php?pid=5135