题解 | #木棍游戏#

C.观察到n只有8,dfs爆搜即可 实际只有2^20次方根本超不了

#include<bits/stdc++.h>
using namespace std;
int vis[10];
double ans;
int num[10];
int n;
bool check(int a[]){
    if(a[1]+a[2]<=a[3]||a[2]+a[3]<=a[1]||a[1]+a[3]<=a[2])
       return 0;
    return 1;
}
double dis(int a[]){
    double p = (a[1]+a[2]+a[3])/2;
    return sqrt(p*(p-a[1])*(p-a[2])*(p-a[3]));
}
void dfs(int now,int a[],int f,int sum){
    if(f==4)
    {
        if(check(a))
        ans = max(ans,dis(a));
        return;
    }
    if(now==n+1){
        if(sum==0)
            return;
        a[f] = sum;
        dfs(1,a,f+1,0);
        return;
    }
    dfs(now+1,a,f,sum);
    if(!vis[now]){
        vis[now] = 1;
        dfs(now+1,a,f,sum+num[now]);
        vis[now] = 0;
    }
}
int main()
{
    cin>>n;
    int a[4] = {0};
    for(int i = 1;i<=n;++i)
       cin>>num[i];
    dfs(1,a,1,0);
    if(ans<0.0000001)
        cout<<-1<<endl;
    else printf("%.1lf",ans);
    return 0;
}