题解 P1284 【三角形牧场】

· · 题解

来一发记(chun)忆(bao)化(li)搜索

我们把三角形的三条边当做搜索的变量。

那么当我们知道其中两个边的长度的话，就可以推出第三条边的长度。

对于每一个木棒，我们都有三种策略

1.加到第一条边yi+a[i],er,sum-(yi+a[i]+er)

2.加到第二条边yi,er+a[i],sum-(yi+er+a[i])

3.加到第三条边yi,er,sum-(yi+er)

然后记忆化搜索就好了!

注意一个问题，这题需要用hash判重，

我们将各个边都乘上一个不同切不会重复的权值就好

（用map会超时。数组要开大！）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<map>
#define lli long long int 
using namespace std;
const int MAXN=10000001;
void read(int &n)
{
    char c='+';int x=0;bool flag=0;
    while(c<'0'||c>'9')
    {c=getchar();if(c=='-')flag=1;}
    while(c>='0'&&c<='9')
    {x=x*10+(c-48);c=getchar();}
    flag==1?n=-x:n=x;
}
int n;
int fi,se;
int vis[MAXN];
int sum=0;
int a[MAXN];
int happen[MAXN];
double ans=-1;
map<string,bool>mp;
double calc(double yi,double er,double san)
{
    if(min(min(yi,er),min(er,san))+min(min(yi,er),min(er,san))>max(max(yi,er),max(er,san)))
    {
        double p=(yi+er+san)/2;
        return sqrt(p*(p-yi)*(p-er)*(p-san));    
    }
    else
    return -1;
}
int comp(const int a,const int b)
{
    return a<b;
}
void dfs(int yi,int er,int san)
{
    if(happen[yi*1500+er*150+san])
        return ;
    happen[yi*1500+er*150+san]=1;
    if(yi+er+san==sum&&yi!=0&&er!=0&&san!=0)
    {
        double hh=calc(yi,er,san);
        if(hh>ans)
        ans=calc(yi,er,san);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            vis[i]=1;
            dfs(yi+a[i],er,sum-(yi+a[i]+er));
            dfs(yi,er+a[i],sum-(yi+er+a[i]));
            vis[i]=0;
            dfs(yi,er,sum-(yi+er));
        }
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(a[i]); sum+=a[i];    
    }
    sort(a+1,a+n+1,comp);// 排序是为了方便调试 
    dfs(0,0,0);
    if(ans==-1)
    { printf("-1"); return 0;}
    ans=ans*100.0;
    printf("%d",(int)ans);
    return 0;
}