首页 > 代码库 > 洛谷 P1284 三角形牧场
洛谷 P1284 三角形牧场
题目描述
和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师Hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40)块木板，每块的长度Li(1≤Li≤40)都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。
请帮助Hei小姐构造这样的牧场，并计算出这个最大牧场的面积。
输入输出格式
输入格式：
第1行：一个整数N
第2..N+1行：每行包含一个整数，即是木板长度。
输出格式：
仅一个整数：最大牧场面积乘以100然后舍尾的结果。如果无法构建，输出-1。
输入输出样例
输入样例#1：
511334
输出样例#1：
692
说明
样例解释：692=舍尾后的（100×三角形面积），此三角形为等边三角形，边长为4。
思路：
f[i][j][k]表示用i块木板是否可以组成的j长度和k长度的三角形
不断地将下一块木板分别加到j上和k上，能构成三角形就更新答案
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace std; 5 int n,sum; 6 double ans; 7 int l[50]; 8 bool f[45][1601][1601]; 9 int qread()10 {11 int x=0,j=1;12 char ch=getchar();13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)j=-1;ch=getchar();}14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15 return x*j;16 }17 bool can(int a,int b,int c)18 {19 if(a+b>c && b+c>a && a+c>b)20 return 1;21 return 0;22 }23 double s(int a,int b,int c)24 {25 double p=double(a+b+c)/2;26 return sqrt(p*(p-a)*(p-b)*(p-c))*100;27 }28 int main()29 {30 n=qread();31 f[0][0][0]=1;32 for(int i=1;i<=n;i++)33 {34 l[i]=qread();35 sum+=l[i];36 }37 for(int i=1;i<=n;i++)38 for(int j=0;j<=sum/2+1;j++)39 for(int k=0;k<=sum/2+1;k++)40 if(f[i-1][j][k])41 {42 f[i][j][k]=1;43 f[i][j+l[i]][k]=1;44 f[i][j][k+l[i]]=1;45 if(can(j+l[i],k,sum-j-l[i]-k))46 ans=max(ans,s(j+l[i],k,sum-j-l[i]-k));47 if(can(j,k+l[i],sum-j-k-l[i]))48 ans=max(ans,s(j,k+l[i],sum-j-k-l[i]));49 }50 if(int(ans)<=0.0)51 printf("-1");52 else printf("%d",int(ans));53 return 0;54 }
洛谷 P1284 三角形牧场
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。