题解

https://www.luogu.org/problemnew/solution/P1284?page=2

代码

#include<bits/stdc++.h>
const int N=50;
const int L=800+10;
using namespace std;

int n,a[N],sum;
double ans;
bool f[L][L];

bool check(int x,int y,int z) 
{
    if(x+y>z&&x+z>y&&y+z>x) return 1;
    return 0;
}

double work(double x,double y,double z)
{
    double p=(x+y+z)/2;
    return sqrt(p*(p-x)*(p-y)*(p-z));
}

int main()
{
    int i,j,k;
    cin>>n;
    for(i=1;i<=n;i++){cin>>a[i]; sum+=a[i];}//用sum记录周长 
    f[0][0]=1;
    for(k=1;k<=n;k++)
      for(i=sum/2;i>=0;i--)//从周长的一半开始循环 
        for(j=sum/2;j>=0;j--)
        {
          if(i-a[k]>=0&&f[i-a[k]][j]) f[i][j]=1;
          if(j-a[k]>=0&&f[i][j-a[k]]) f[i][j]=1;
          //if(f[i][j]) f[i][j]=1;
          //这句可以省略 
        }
    ans=-1;
    for(i=sum/2;i>0;i--)
      for(j=sum/2;j>0;j--)
      {
        if(!f[i][j]) continue;
        if(!check(i,j,sum-i-j)) continue;//判断能否构成三角形
        ans=max(ans,work(i,j,sum-i-j));//更新答案 
      }
    if(ans!=-1) cout<<(long long)(ans*100)<<endl;
    else cout<<ans<<endl;
    return 0;
}