puzzleUp风味题 Vol.5
【组装三角】
给予50个线段，长度分别为1~50。
组成任意数量的直角三角形。
问这些直角三角形的最大总合面积为？
线段不能裁接凹折
三角形之间不能共线
若题目给1~20的线段，则答案为162
(3,4,5)(8,15,17)(12,16,20)

长度1跟2是不可能组成直角三角形的，无视就好:)

程式列出毕氏三元数，再用纸笔初步凑出 1932如果不考虑毕氏三元数可能出现的潜在关系programUp 起来是个 weighted independent set 问题要处理的图是这个 https://imgur.com/VyVurkQ.png

1932还差一点点哦

上面那张图多算了 (20, 48, 52)，不过跑起来结果一样因为没有用到那组是有没考虑到的组装方式吗(思找到问题了，1944

1944正解

新的图要手算感觉麻烦许多

我找到 1944, 还不确定是不是最大hmmmm啊, 找到 1932 了...还在想这种 local max 应该要出现的我是整理出 (9,12,15) (12,16,20) (15,20,25) 最多取其一从这里去找, 1944 是选 (15,20,25) 得到的最大值1932 则是都不选的 local max主要是 (30,40,50) 的位置太尴尬, 取和不取的条件不够多又被 (14,48,50) (18,24,30) (24,32,40) 两边夹从那边出发的分支完全动不到上五楼提到的那一团

我是用 (m^2-n^2, 2mn, m^2+n^2) 找毕氏三元数没注意到这只保证可以找出互质的，所以才算出 1932 XD那张图里列的是用这个公式可以找出的那些

哦, 你是找所有 (m, n) 而不是用基本三元数乘 k 倍...

对XD

所以就正好漏掉了包含 (15,20,25) 的几个这样吗 XD

有包含 (12,16,20)，不过找最大值的时候不会取到