# P1284 三角牧场

www.MyException.Cn  网友分享于：2013-09-17  浏览：0次
P1284 三角形牧场

```5
1
1
3
3
4
```

```692
```

# 分析：

S:=sqrt(pi*(pi-a)*(pi-b)*(pi-c))

1、dp

dp[i,j]:=dp[i,j] or dp[i-d[k],j] or dp[i,j-d[k]];

``` 1 var ans:double;
2     i,j,k,sum,n:longint;
3     d:array[1..100000]of longint;
4     dp:array[0..1000,0..1000]of boolean;
5 function max(a,b:double):double;
6 begin
7  if a<b then exit(b)
8  else exit(a);
9 end;
10 function solve(a,b,c:longint):double;
11 var p:double;
12 begin
13  p:=(a+b+c)/2;
14  if (c<=0)or(a<=0)or(b<=0) then exit(-1);
15  if (a+b<=c)or(b+c<=a)or(a+c<=b) then exit(-1);
16  exit(sqrt(p*(p-a)*(p-b)*(p-c)));
17 end;
18 begin
19  ans:=0;
21  for i:=1 to n do begin read(d[i]); inc(sum,d[i]); end;
22  fillchar(dp,sizeof(dp),false);
23  dp[0,0]:=true;
24  for k:=1 to n do
25   for i:=sum downto 0 do
26    for j:=sum downto 0 do begin
27   if i>=d[k] then dp[i,j]:=dp[i,j] or dp[i-d[k],j];
28   if j>=d[k] then dp[i,j]:=dp[i,j] or dp[i,j-d[k]];
29   if dp[i,j] then ans:=max(ans,solve(i,j,sum-i-j));
30  end;
31  if ans=0 then writeln(-1)
32  else writeln(trunc(ans*100));
33 end.```

2、记忆化搜索

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)

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

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #include<map>
8 #define lli long long int
9 using namespace std;
10 const int MAXN=10000001;
12 {
13     char c='+';int x=0;bool flag=0;
14     while(c<'0'||c>'9')
15     {c=getchar();if(c=='-')flag=1;}
16     while(c>='0'&&c<='9')
17     {x=x*10+(c-48);c=getchar();}
18     flag==1?n=-x:n=x;
19 }
20 int n;
21 int fi,se;
22 int vis[MAXN];
23 int sum=0;
24 int a[MAXN];
25 int happen[MAXN];
26 double ans=-1;
27 map<string,bool>mp;
28 double calc(double yi,double er,double san)
29 {
30     if(min(min(yi,er),min(er,san))+min(min(yi,er),min(er,san))>max(max(yi,er),max(er,san)))
31     {
32         double p=(yi+er+san)/2;
33         return sqrt(p*(p-yi)*(p-er)*(p-san));
34     }
35     else
36     return -1;
37 }
38 int comp(const int a,const int b)
39 {
40     return a<b;
41 }
42 void dfs(int yi,int er,int san)
43 {
44     if(happen[yi*1500+er*150+san])
45         return ;
46     happen[yi*1500+er*150+san]=1;
47     if(yi+er+san==sum&&yi!=0&&er!=0&&san!=0)
48     {
49         double hh=calc(yi,er,san);
50         if(hh>ans)
51         ans=calc(yi,er,san);
52     }
53     for(int i=1;i<=n;i++)
54     {
55         if(vis[i]==0)
56         {
57             vis[i]=1;
58             dfs(yi+a[i],er,sum-(yi+a[i]+er));
59             dfs(yi,er+a[i],sum-(yi+er+a[i]));
60             vis[i]=0;
61             dfs(yi,er,sum-(yi+er));
62         }
63     }
64 }
65 int main()
66 {
68     for(int i=1;i<=n;i++)
69     {
71     }
72     sort(a+1,a+n+1,comp);// 排序是为了方便调试
73     dfs(0,0,0);
74     if(ans==-1)
75     { printf("-1"); return 0;}
76     ans=ans*100.0;
77     printf("%d",(int)ans);
78     return 0;
79 }```

3、贪心+随机化

``` 1 var
2   b:array[1..3] of longint;
3   i,n,p,t,j,k,top,max:longint;
4   a:array[0..100000] of longint;
5 function jisuan(x,y,z:longint):longint;
6 var
7   k,c:real;
8   t:longint;
9 begin
10   c:=(x+y+z)/2;
11   if (c-x<=0) or (c-y<=0) or (c-z<=0) then exit(-1);
12   k:=sqrt((c-x)*(c-y)*(c-z)*c)*100;
13   t:=trunc(k);
14   exit(t);
15 end;
16 procedure suiji;
17 var
18   i,t:longint;
19 begin
20   for i:=1 to n do begin
21     t:=random(n);//随机化
22     a[0]:=a[t];
23     a[t]:=a[i];
24     a[i]:=a[0];
25   end;
26 end;
27 begin
28   max:=-2;
29   randomize;
31   for i:=1 to n do begin
33   end;
34   for i:=1 to 100000 do begin
35     suiji;
36     b[1]:=a[1];
37     b[2]:=a[2];
38     b[3]:=a[3];
39     k:=3;
40     while k<=n do begin
41       for j:=1 to 2 do begin
42         for t:=2 to 3 do begin
43           if b[j]>b[t] then begin
44             p:=b[j]; b[j]:=b[t]; b[t]:=p;
45           end;
46         end;
47       end;
48       inc(k);
49       b[1]:=b[1]+a[k];
50     end;
51     top:=jisuan(b[1],b[2],b[3]);//贪心
52     if top>max then max:=top;
53   end;
54   writeln(max);
55 end.```