首页 > 代码库 > hdu 5135 Little Zu Chongzhi's Triangles

hdu 5135 Little Zu Chongzhi's Triangles

2024-11-05 22:16:01   205人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=5135

题意：给你N个木棍的长度，然后让你组成三角形，问你组成的三角形的和最大是多少？

思路：先求出可以组成的所有的三角形，然后状压dp就可以。求所有的三角形也可以用状压，也可以三重循环求。

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define maxn 1<<13 6 using namespace std; 7  8  9 int n;10 int a[20];11 int b[20];12 int cc[maxn];13 double ss[maxn];14 double ans;15 double dp[maxn];16 17 bool vis[20];18 19 20 int main()21 {22     while(scanf("%d",&n)!=EOF)23     {24         if(n==0) break;25         memset(cc,0,sizeof(cc));26         memset(dp,0,sizeof(dp));27         memset(ss,0,sizeof(ss));28         for(int i=0; i<n; i++)29         {30             scanf("%d",&a[i]);31         }32         int t1=0;33         for(int i=0; i<(1<<n); i++)34         {35             memset(b,0,sizeof(b));36             int cnt=0;37             for(int j=0; j<n; j++)38             {39                 if((1<<j)&i) cnt++;40             }41             if(cnt==3)42             {43                 int c=0;44                 for(int j=0; j<n; j++)45                 {46                     if((1<<j)&i)47                     {48                         b[c++]=a[j];49                     }50                 }51                 if((b[0]<b[1]+b[2])&&(b[1]<b[0]+b[2])&&(b[2]<b[0]+b[1]))52                 {53                     cc[t1]=i;54                     double p=(double)((b[0]+b[1]+b[2])*1.0/2);55                     double s=sqrt(p*(p-b[0]*1.0)*(p-b[1]*1.0)*(p-b[2]*1.0));56                     ss[t1++]=s;57                 }58             }59         }60         double ans=0;61         for(int i=0; i<(1<<n); i++)62         {63             for(int j=0; j<t1; j++)64             {65                 if((i&(cc[j]))==0)66                 {67                     dp[i|cc[j]]=max(dp[i|cc[j]],dp[i]+ss[j]);68                     ans=max(ans,dp[i|cc[j]]);69                 }70             }71         }72         printf("%.2lf\n",ans);73     }74     return 0;75 }
View Code

 

hdu 5135 Little Zu Chongzhi's Triangles


联系
我们