题目描述

和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师Hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40)块木板，每块的长度Li(1≤Li≤40)都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。

请帮助Hei小姐构造这样的牧场，并计算出这个最大牧场的面积。

输入输出格式

输入格式：

 

第1行：一个整数N

第2..N+1行：每行包含一个整数，即是木板长度。

 

输出格式：

 

仅一个整数：最大牧场面积乘以100然后舍尾的结果。如果无法构建，输出-1。

 

输入输出样例

输入样例#1：

511334

输出样例#1：

692

说明

样例解释：692=舍尾后的（100×三角形面积），此三角形为等边三角形，边长为4。

————————————————————我是分割线————————————————————————

dp题目，用dp[i][j][k]表示前i块木板是否能拼成j、k长度，即可。

记得用海伦公式

1 /* 2 Problem: 3 OJ:  4 User: S.B.S. 5 Time:  6 Memory: 7 Length: 8 */ 9 10 #include
      
       11 #include
       
        12 #include
        
         13 #include
         
          14 #include
          
           15 #include
           
            16 #include
            
             17 #include
             
              18 #include
              
               19 #include
               
                20 #include
                
                 21 #include
                 
                  22 #include
                  
                   23 #include
                   
                    24 #define F(i,j,k) for(int i=j;i<=k;++i)25 #define M(a,b) memset(a,b,sizeof(a))26 #define FF(i,j,k) for(int i=j;i>=k;i--)27 #define maxn 1000128 #define inf 0x3f3f3f3f29 #define maxm 400130 #define mod 99824435331 using namespace std;32 int read(){33 int x=0,f=1;char ch=getchar();34 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();}35 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}36 return x*f;37 }38 int n,m;39 bool dp[2000][2000];40 int d[41];41 int sum=0;42 double ans=-1.0;43 inline double solve(int a,int b,int c)44 {45 if(c==0||a+b<=c||b+c<=a||a+c<=b) return -1;46 double p=(a+b+c)/2.0;47 return 100*sqrt(p*fabs(p-a)*fabs(p-b)*fabs(p-c));48 }49 int main()50 {51 std::ios::sync_with_stdio(false);//cout<
                    
                     <
                     
                      <
                      
                       >n;58 F(i,1,n) cin>>d[i],sum+=d[i];59 F(i,1,n) dp[0][0]=true;60 F(k,1,n)FF(i,sum,0)FF(j,sum,0){61 if(i>=d[k]) dp[i][j]=dp[i][j]||dp[i-d[k]][j];62 if(j>=d[k]) dp[i][j]=dp[i][j]||dp[i][j-d[k]];63 if(k==n&&i&&j&&dp[i][j]) ans=max(ans,solve(i,j,sum-i-j));64 }65 cout<<(int)(ans)<