首页 > 代码库 > (DP) poj 1948

(DP) poj 1948

2024-11-24 20:12:39   203人阅读

Triangular Pastures
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 6783 Accepted: 2201

Description

Like everyone, cows enjoy variety. Their current fancy is new shapes for pastures. The old rectangular shapes are out of favor; new geometries are the favorite. 

I. M. Hei, the lead cow pasture architect, is in charge of creating a triangular pasture surrounded by nice white fence rails. She is supplied with N (3 <= N <= 40) fence segments (each of integer length Li (1 <= Li <= 40) and must arrange them into a triangular pasture with the largest grazing area. Ms. Hei must use all the rails to create three sides of non-zero length. 

Help Ms. Hei convince the rest of the herd that plenty of grazing land will be available.Calculate the largest area that may be enclosed with a supplied set of fence segments. 

Input

* Line 1: A single integer N 

* Lines 2..N+1: N lines, each with a single integer representing one fence segment‘s length. The lengths are not necessarily unique. 

Output

A single line with the integer that is the truncated integer representation of the largest possible enclosed area multiplied by 100. Output -1 if no triangle of positive area may be constructed. 

Sample Input

511334

Sample Output

692

Hint

[which is 100x the area of an equilateral triangle with side length 4] 
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<cstdlib>using namespace std;int n,a[50],dp[810][810],sum,p,ans=-1;int main(){      memset(dp,0,sizeof(dp));      scanf("%d",&n);      dp[0][0]=1;      for(int i=1;i<=n;i++)            scanf("%d",&a[i]),sum+=a[i];      for(int i=1;i<=n;i++)      {           for(int j=sum/2;j>=0;j--)           {                 for(int k=j;k>=0;k--)                 {                       if((j>=a[i]&&dp[j-a[i]][k])||(k>=a[i]||dp[j][k-a[i]]))                       {                             dp[j][k]=1;                       }                 }           }      }      for(int i=sum/2;i>=1;i--)      {            for(int j=i;j>=1;j--)            {                  if(dp[i][j])                  {                        int k=sum-i-j;                        double p=sum*1.0/2;                        if(i+j>k&&i+k>j&k+i>j)                        {                              int temp=(int)(sqrt(p*(p-i)*(p-j)*(p-k))*100);                              if(temp>ans)                                    ans=temp;                        }                  }            }      }      printf("%d\n",ans);      return 0;}

　　

(DP) poj 1948


联系
我们