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

最新文章

  1. iOS学习-UIButton的imageView和titleLabel
  2. 使用配置文件来配置JDBC连接数据库
  3. TortoiseGit 连接Git服务器不用每次输入用户名和密码的方法
  4. 总结.NET 中什么时候用 Static
  5. windows路径操作API函数
  6. 使用树莓派和kali Linux打造便携式渗透套件
  7. [Java]获取Window界面的标题栏的高度大小
  8. struts2的namespace
  9. Genymotion - 强大好用高性能的 Android 模拟器 (在电脑流畅运行APK安卓软件游戏的利器)
  10. Java IO学习笔记
  11. hdoj 2222 Keywords Search(AC自动机)
  12. css+js整站变灰(兼容IE7+)
  13. fzu 2257 saya的小熊饼干
  14. px、pt、em、rem 的区别
  15. java基础(八)-----深入解析java四种访问权限
  16. Random类 一般跟生成随机数有关
  17. 移动端与pc端如何用localStorage实现历史纪录?
  18. 【Python】hasattr() getattr() setattr() 使用方法详解
  19. oracle 备份数据库,导出数据库
  20. 使用 kubeadm 搭建 kubernetes1.10 集群

热门文章

  1. Asp.Net WebApi核心对象解析(下篇)
  2. 前端学HTTP之Web主机托管
  3. 浅谈javascript面向对象
  4. centos使用yum安装软件的时候出现了undefined symbol: CRYPTO_set_locking_callback
  5. WinForm实现对权限菜单进行管理
  6. Android学习 之 startActivityForResult 和 onActivityResult
  7. 网站开发常用jQuery插件总结(七)背景插件backstretch
  8. [JavaScript] js 复制到剪切板
  9. Django学习笔记(三)—— 型号 model
  10. C++设计模式-参考资料
  11. RSA实践指南
  12. Python学习——(1)Centos安装Flask
  13. Docker三十分钟快速入门(下)
  14. MySQL基于binlog主从复制
  15. vue实现实时监听文本框内容的变化(最后一种为原生js)
  16. django之全局默认设置查看及admin语言设置
  17. svn 从文件上次修改以来没有任何文件修改或加入。
  18. Python装饰器实现异步回调
  19. C++ 实现sqilte创建数据库插入、更新、查询、删除
  20. Struts2(二)工作原理