P15053

三角形牧场

难度 5 级小学动态规划入门背包DP 海伦公式

讨论统计 8通过 16提交 50%通过率旧版界面

时间限制 1 秒 内存限制 128 MB

题目描述

奶牛建筑师 Hei 想建造围有漂亮白色栅栏的三角形牧场。她拥有 $n$ 块木板，每块的长度 $l_i$ 都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。

请帮助 Hei 小姐构造这样的牧场，并计算出这个最大牧场的面积。

第 $1$ 行：一个整数 $n$ ；

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $l_i$ 表示第 $i$ 块木板的长度。

仅一个整数：最大牧场面积乘以 $100$ 然后舍尾的结果。如果无法构建，输出 $-1$ 。

样例 1

输入

输出

$692=\text{舍尾后的}(100\times\text{三角形面积})$ ，此三角形为等边三角形，边长为 $4$ 。

对于 $100\%$ 的数据，保证 $3\le n\le40$ ， $1\le l_i\le40$ 。

luogu

上一题下一题