作者fatcat8127 (胖胖猫)
看板Prob_Solve
标题[问题] DFS剪枝
时间Thu Mar 14 16:14:52 2019
一开始看到想到的解法是改编於 uva10364 的题目。
(1) 将所有的线段加总後的总长度做质因数分解，只保留因数的数值大於等於最大线段长
的数值 这些因数都可能是筷子的长度。
(2) 将输入的线段由大到小排列，因数部分由小到大排列。 枚举所有可能的因数直到成功
成功的定义为可以用所有的线段组出刚好边长。
但是 d375-uva10364 的题目测资范围只有20个片段组成，
这题最多会到达50个， 如果挑战失败意谓着会把所有可能尝试过都无法组出来，
所以需要更好的剪枝来达成。
b597: Stickst(
https://zerojudge.tw/ShowProblem?problemid=b597)
这是我写的Code:
https://www.codepile.net/pile/n1V8MnyY
不过会吃TLE，想问说还有哪部分可以剪枝但没注意到。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.208.164
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1552551296.A.117.html
1F：推 rareone: 1. 尝试从最长开始排到最短的话呢，可以 greedy 如果有 [ 03/19 20:01
2F：→ rareone: 2, 3] 跟 [5] 的 sticks 可用，永远先考虑拿 [5] 03/19 20:01
3F：→ rareone: 2. 可以 DP 记住 [目前的根数] [iter 到哪一根] [目前这 03/19 20:02
4F：→ rareone: 一根iter 多长] 03/19 20:02
5F：推 rareone: 唔 我2. 好像有细节上的 bug 再想想 03/19 20:04
6F：推 rareone: 2. 用 bitmask 双向进行 BFS，状态存 set，每次排出来看 03/19 20:17
7F：→ rareone: 一下他的 complement是不是在另一头BFS走过了 03/19 20:17
8F：→ rareone: BTW 检定性质的 bi-BFS 有随机性的算法，就是两端随便生 03/19 20:20
9F：→ rareone: m 条 k/2-path 然後 03/19 20:20
10F：→ rareone: meet-in-the-middle 比对 03/19 20:21
11F：推 CathyP: 先排序然後从最小的因数开始测,去掉不可能的情形 03/20 23:01
12F：→ CathyP: 1. 除出来的组数超过阵列大小 2. 阵列最大值大於因数 03/20 23:02
13F：→ CathyP: 进行DFS时1.跳过重复的起点2.false的情形如果目前和为零 03/20 23:04
14F：→ CathyP: 表示不可能完成分组,直接early return 03/20 23:04
15F：→ CathyP: 3.每组的起点都由阵列中未使用的最大值开始 03/20 23:05
16F：→ fatcat8127: 可以理解因数必须大於等於从片段中最长边长 03/21 00:27
17F：→ fatcat8127: 但DFS的实作不是很清楚 03/21 00:28
18F：推 CathyP: 比方说A = [1,1,1,1,2,3],最初的DFS从sum = 0, pos = 0跑 03/21 09:39
19F：→ CathyP: 这层的DFS会以for (int i = pos;)开始测A[i] + sum 03/21 09:41
20F：→ CathyP: 同一层DFS上一个拿来测的叫A[j]好了, 当A[i] == A[j]跳过 03/21 09:42
21F：→ CathyP: 意思是说同一个位置不需要测试相同长度的A[i] 03/21 09:43
22F：→ CathyP: 另外假设该层DFS sum = 0,但找不到解,就表示没有任何组合 03/21 09:46
23F：→ CathyP: 可以满足条件,就可以early return 03/21 09:46
24F：→ fatcat8127: 感谢大大 虽然不吃TLE 不过还是WA 不知道哪边挂掉 03/21 15:21
25F：→ fatcat8127: 第五组我会输出83不过答案是1411，第七组是36答案是48 03/21 15:22
27F：→ fatcat8127: 刚刚发现dfs写错，调整後还是tle QQ 03/21 15:59
28F：推 CathyP: 质因数分解那一段不需要做, 直接从1开始测试 03/21 17:36
29F：→ CathyP: use array不需要每次都memset,一开始做一次就好 03/21 17:38
30F：→ CathyP: 因为当A[i]不能拿来用,应该把use[i]还原 03/21 17:39
31F：推 CathyP: DFS中的start应该由阵列尾端开始(Greedy) 03/21 17:44
32F：→ CathyP: 完成一个Group後,由阵列尾端往前找尚未使用的 03/21 17:45
33F：→ CathyP: 当下一层DFS的起点 03/21 17:45
34F：→ CathyP: nowLen=0时,DFS又回传false就要early return了 03/21 17:47
35F：→ CathyP: 不需要继续iterate下去因为这表示该A[i]找不到任何解 03/21 17:48
36F：→ CathyP: 变数应该避免使用global variable, 容易错 03/21 17:50
37F：→ fatcat8127: 质因数分解的目的不是必须的吗?这样才能保证找到可以 03/22 13:49
38F：→ fatcat8127: 整除边长的边数和剪枝。for回圈外面有个return false 03/22 13:49
39F：→ fatcat8127: 就是当现在不存一条边满足时就回传false 03/22 13:49
41F：→ fatcat8127: /WKrglxeG 03/22 13:52
42F：推 cutekid: 第 39 行 use[i] = 0; 下面增加一句 03/22 14:41
43F：→ cutekid: if(nowLen == 0) break; 03/22 14:41
44F：→ fatcat8127: 感谢 cutekid 和 CathyP 两位大大耐心的指导和协助。 03/22 15:05
45F：→ fatcat8127: 感谢第一位回覆我的rareone大大，但我不太会双向BFS 03/22 15:12
46F：→ fatcat8127: 和记忆化搜索方式，大概知道你说的方式 03/22 15:12
48F：→ fatcat8127: 阿 2ms版本应该是测资较弱没测出来，测资 : 15 34 38 03/22 18:20
49F：→ fatcat8127: 10 44 45 7 13 30 44 43 47 43 27 38 5 03/22 18:20
50F：→ fatcat8127: 答案是117 03/22 18:20
51F：推 FRAXIS: 当你在测试 edgeLen 可不可行的时候 03/23 11:13
52F：→ FRAXIS: 可以用 DP 吗？ 先找找有没有一个 subset sum = edgeLen 03/23 11:14
53F：→ FRAXIS: 有的话 就拿掉那个 subset 然後 repeat 直到所有元素都 03/23 11:14
54F：→ FRAXIS: 用完为止， subset sum 用 DP 应该很容易作 03/23 11:14
55F：→ fatcat8127: 应该无法，同样是我举例的测资，如果先移除(43,44,30 03/23 16:26
56F：→ fatcat8127: )和(47,45,5,7,13)剩余的片段无法构成两个117 03/23 16:26
57F：推 CathyP: 你的测资答案是161才对喔, 总和是483 03/23 18:32
59F：→ fatcat8127: 第一个15是输入15个数字的意思 03/23 23:57
60F：→ fatcat8127: 第40行程式码是线性侦查目前的线段长度是不是总长度 03/24 00:21
61F：→ fatcat8127: 的因数，因为测资的总长度不超过2500所以无论是线性 03/24 00:21
62F：→ fatcat8127: 或是先做质因数分解找因数，时间差异不大。 03/24 00:21
63F：推 FRAXIS: 那如果用 DP 先找出所有的 subset sum 然後再 DFS ？ 03/24 06:15
64F：→ FRAXIS: 只是这样做起来比较麻烦就是了 03/24 06:15
65F：推 FRAXIS: 从你原本的程式看起来 把 unused set 用 BST 存起来 03/24 06:27
66F：→ FRAXIS: 会不会比较方便找解答？ 03/24 06:27
67F：推 CathyP: 你的没跑出117是出在line 39那边没检查回传值所以错误 03/24 21:43
68F：→ fatcat8127: 感谢C大 那边如果判断失误应该要还原use[i]的状态 03/25 07:55
69F：→ fatcat8127: 根据FRAXIS大大的想应该是找出所有可以构成现在边长 03/28 13:28
70F：→ fatcat8127: 用到的所有状态集合，从这堆集合中找出一组存在每个 03/28 13:28
71F：→ fatcat8127: 片段只会用一次，这个问题等价於ZJ-a207需要用dancin 03/28 13:28
72F：→ fatcat8127: g link 解且存在状态过多的风险。 我先理解一下a207 03/28 13:28
73F：→ fatcat8127: 的题目.... 03/28 13:28