三角形牧场

题目描述

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

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

输入格式

第 $1$ 行：一个整数 $n$；

第 $2$ 到第 $(n+1)$ 行，每行一个整数，第 $(i+1)$ 行的整数 $l_i$ 表示第 $i$ 块木板的长度。

输出格式

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

样例 #1

样例输入 #1

5
1
1
3
3
4

样例输出 #1

692

提示

样例输入输出 1 解释

$692=\text{舍尾后的}(100\times \text{三角形面积})$，此三角形为等边三角形，边长为 $4$。

数据规模与约定

对于 $100\%$ 的数据，保证 $3\le n\le 40$，$1\le l_i\le 40$。

明显 $dfs$ 的时间复杂度是 $O(3^{40})$

void dfs(int u,int A,int B,int C){
    
    if(u>n){
    
    	if(A+B>C && A+C>B && B+C>A){
    
	        double p = (A+B+C)/2;
	        double s = sqrt(p*(p-A)*(p-B)*(p-C));
	        ans = max(ans, (ll)(s*100));
        }
        return ;
    }
    dfs(u+1,A+a[u],B,C);
    dfs(u+1,A,B+a[u],C);
    dfs(u+1,A,B,C+a[u]);
}

容易想到 $f[i][j][k]$ 表示使用前 $i$ 个木棍，第1条边的边长是 $j$, 第2条边的边长是 $k$ 的三角形能否围成。40 * 800 * 800 是可以接受的。

自己写的时候遇到了一个大坑，有些奇怪，没有判断3边关系也A了，是数据水了吗？

当然此题可以改2维。

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <stack>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e6+10;
int n,m,_;
int a[50],f[50][810][810];
double ans,sum;
double area(double a,double b){
    
    double c = sum-a-b;
    double p = (a+b+c)/2;
    double s = sqrt(p*(p-a)*(p-b)*(p-c));
    return s;
}

void solve(){
    
    cin>>n;
    fo(i,1,n){
    
        cin>>a[i];
        sum+=a[i];
    }
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
    
        for(int j=sum/2;j>=0;j--){
    
            for(int k=sum/2;k>=0;k--){
    
                f[i][j][k] |= f[i-1][j][k];
                if(j-a[i]>=0){
    
                    f[i][j][k] |= f[i-1][j-a[i]][k];
                }
                if(k-a[i]>=0){
    
                    f[i][j][k] |= f[i-1][j][k-a[i]];
                }
            }
        }
    }
    ans = -1;
	for(int k=1;k<=n;k++){
    
		for(int i=sum/2;i>0;i--)
			for(int j=sum/2;j>0;j--)
			{
    
				if(!f[k][i][j]) continue;
				ans=max(ans,area(i,j));//更新答案 
			}
	}
	if(ans!=-1){
    
		cout<<(ll)(ans*100)<<endl;		
	}
	else
    cout<<ans<<endl;
}

int main(){
    
	solve();
	return 0;
}