题解 | #木棍游戏#
满意的数字
https://ac.nowcoder.com/acm/contest/11220/A
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;
}
