作者buffalobill (水牛比尔)
看板puzzle
标题[问题] 组装三角
时间Mon Aug 31 09:02:34 2020
puzzleUp风味题 Vol.5
【组装三角】
给予50个线段，长度分别为1~50。
组成任意数量的直角三角形。
问这些直角三角形的最大总合面积为？
线段不能裁接凹折
三角形之间不能共线
若题目给1~20的线段，则答案为162
(3,4,5)(8,15,17)(12,16,20)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 60.251.148.94 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1598835756.A.5D3.html
1F：→ buffalobill: 长度1跟2是不可能组成直角三角形的，无视就好:) 08/31 09:03
※ 编辑: buffalobill (60.251.148.94 台湾), 08/31/2020 09:43:14
2F：推 arthurduh1: 程式列出毕氏三元数，再用纸笔初步凑出 1932 08/31 09:45
3F：→ arthurduh1: 如果不考虑毕氏三元数可能出现的潜在关系 08/31 09:47
4F：→ arthurduh1: programUp 起来是个 weighted independent set 问题 08/31 09:47
6F：→ buffalobill: 1932还差一点点哦 08/31 14:09
7F：推 arthurduh1: 上面那张图多算了 (20, 48, 52)，不过跑起来结果一样 08/31 14:44
8F：→ arthurduh1: 因为没有用到那组 08/31 14:45
9F：→ arthurduh1: 是有没考虑到的组装方式吗(思 08/31 14:45
10F：推 arthurduh1: 找到问题了，1944 08/31 15:01
11F：→ buffalobill: 1944正解 08/31 15:05
12F：推 arthurduh1: 新的图要手算感觉麻烦许多 08/31 15:13
13F：推 LPH66: 我找到 1944, 还不确定是不是最大 08/31 15:13
14F：→ LPH66: hmmmm 08/31 15:13
15F：推 LPH66: 啊, 找到 1932 了...还在想这种 local max 应该要出现的 08/31 15:35
16F：→ LPH66: 我是整理出 (9,12,15) (12,16,20) (15,20,25) 最多取其一 08/31 15:36
17F：→ LPH66: 从这里去找, 1944 是选 (15,20,25) 得到的最大值 08/31 15:36
18F：→ LPH66: 1932 则是都不选的 local max 08/31 15:36
19F：→ LPH66: 主要是 (30,40,50) 的位置太尴尬, 取和不取的条件不够多 08/31 15:40
20F：→ LPH66: 又被 (14,48,50) (18,24,30) (24,32,40) 两边夹 08/31 15:41
21F：→ LPH66: 从那边出发的分支完全动不到上五楼提到的那一团 08/31 15:42
22F：推 arthurduh1: 我是用 (m^2-n^2, 2mn, m^2+n^2) 找毕氏三元数 08/31 15:43
23F：→ arthurduh1: 没注意到这只保证可以找出互质的，所以才算出 1932 XD 08/31 15:43
24F：→ arthurduh1: 那张图里列的是用这个公式可以找出的那些 08/31 15:44
25F：推 LPH66: 哦, 你是找所有 (m, n) 而不是用基本三元数乘 k 倍... 08/31 15:46
26F：→ arthurduh1: 对XD 08/31 15:46
27F：→ LPH66: 所以就正好漏掉了包含 (15,20,25) 的几个这样吗 XD 08/31 15:47
28F：推 arthurduh1: 有包含 (12,16,20)，不过找最大值的时候不会取到 08/31 15:53