很容易想到dp,f[i,j,k]表示到第i根木棒所组成三条边中两条边长为j,k是否存在
之后找所有满足三角形形成条件的三条边,然后找最大;
但:
如果你朴素的写,很有可能超时,事实上,只要加一些常数优化,就能卡过去
var a,s:array[..] of longint;
f:array[..,..,..] of boolean;
i,j,k,k1,k2,n,l:longint;
ans,p,t:double;
begin
readln(n);
for i:= to n do
begin
readln(a[i]);
s[i]:=s[i-]+a[i];
end;
f[,,]:=true;
k1:=;
k2:=;
for i:= to n do
begin
k1:=k1 xor ;
k2:=k2 xor ;
for j:= to s[i] do
begin
l:=min(j,s[i]-j);
for k:= to l do //常数优化1
begin
if j-a[i]>= then f[k2,j,k]:=f[k2,j,k] or f[k1,j-a[i],k];
if k-a[i]>= then f[k2,j,k]:=f[k2,j,k] or f[k1,j,k-a[i]];
if s[i]-j-k-a[i]>= then f[k2,j,k]:=f[k2,j,k] or f[k1,j,k];
end;
end;
end;
ans:=;
for i:= to s[n]- do
for j:=(s[n] shr )+-j to min(s[n]-j-,j) do //常数优化2:满足三角形
if f[k2,i,j] and (s[n]-i-j>) then
begin
k:=s[n]-i-j;
if (j>=i+k) or (k>=i+j) or (i>=j+k) then continue;
t:=(k+i+j)/;
p:=sqrt(t*(t-i)*(t-j)*(t-k));
ans:=max(ans,p);
end;
if ans= then writeln(-) else writeln(trunc(ans*));
end.
事实上在OI中,多加一些常数优化往往有意想不到的效果!