注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ1948Triangular Pastures题解  

2014-03-10 22:15:08|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                   三角形牧场
                                                  BY   LGS
题目大意:给你N个木板,由所有这些木板组成的三角形面积最大的,输出面积。

题解:这题明白海伦公式:a,b,c为三角形ABC的三条边的长度,设P=(a+b+c)/2;那么三角形面积则为根号(P*(P-a)*(P-b)*(P-c));然后就变成了裸的01双重背包,因为周长都给定的N个数的和,所以只需背包两个数,2维数组。F[1601][1061]BOOL类型。然后时间就是40*1600*1600,中间还有个很小的优化,能0.06秒过的。注意,一个细节坑了我一次,害我调了半天:DOUBLE P=(a+b+c)*1.0/2;注意C++中浮点数类型若直接(a+b+c)/2;直接会取整的。如double q=3/2;那么q=1;所以必须*1.0的精度变成1.5才能AC这题,太坑了!!!!

代码:
#include<cstdio>
#include<cmath>
using namespace std;
int i,j,n,sum,ans,k,t;
bool f[2500][2500];
double q;
int max(int a,int b){return (a>b)?a:b;}
int hl(){return int(sqrt(q*(q-j)*(q-k)*(q-sum+j+k))*100);}
int a[100];
int main()
{
 scanf("%d",&n);sum=0;
 for (i=1;i<=n;i++)
   {scanf("%d",&a[i]);sum+=a[i];}q=sum*1.0/2;
f[0][0]=true;t=0;
for (i=1;i<=n;i++)
      {
                    t+=a[i];
   for (j=t;j>=0;j--)
    for (k=t;k>=0;k--)
        if (f[j][k])
                    {f[j+a[i]][k]=true;
                     f[j][k+a[i]]=true;}
     
      }
 ans=-1;
for (j=1;j<=sum-1;j++)
 for (k=1;k<=sum-1;k++)if (f[j][k]&&(sum-j-k>0))
     if ((2*(j+k)>sum)&&(sum>2*k)&&(sum>2*j)) 
         ans=max(ans,hl()); 
printf("%d",ans);
return 0;
}

  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018