很容易想到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中,多加一些常数优化往往有意想不到的效果!

05-04 07:03