作者MOUOREO (毛毛)
看板Grad-ProbAsk
标题[理工] 资演 OBST
时间Thu Jan 25 12:11:57 2018
想请问大家在算OBST时
Cost矩阵的对角线是放0还是外部成本呢？
一直以来我在算的时候都放外部成本，但我昨天发现资结的算法在计算Cost的时候对角线
都是放0，这样答案会有全部外部成本的差距。
资结跟演算法的定义是不是常常有小出入呢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.242.77.180
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1516853519.A.27A.html
1F：推 q1qip123: 要注意他们的I,j从哪里开始 01/25 12:37
2F：→ q1qip123: 你把例子贴上来 大家会比较好跟你解释 01/25 12:37
3F：→ aggress5566: 外部成本听起来很像社会科学那个xD 要看题目怎麽定 01/25 14:15
4F：→ aggress5566: 义 01/25 14:15
7F：→ MOUOREO: 这题如果放外部成本cost是2.4 01/25 14:37
8F：→ MOUOREO: 如果放0就会如答案所说是2.0 01/25 14:37
9F：推 q1qip123: 这是DS跟ALGO对外部节点定义不同的关系 01/25 19:12
10F：→ q1qip123: 考试的时候 你就把假设写清楚应该就好了 01/25 19:13
11F：推 TMDTMD2487: 我觉得这东西用陈立宇交的方式去算比较简洁(就三个倒 01/25 19:37
12F：→ TMDTMD2487: 三角形的表格 01/25 19:37
13F：→ TMDTMD2487: 然後差别只是失败的成本定义 01/25 19:43
14F：→ TMDTMD2487: dp问题只要搞懂递回的由来跟表格大概的长相，ds跟algo 01/25 19:45
15F：→ TMDTMD2487: 这里的差别也只是递回差一点点，反正先列出递回在作 01/25 19:45
16F：→ TMDTMD2487: 答比较好 01/25 19:45
17F：→ TMDTMD2487: 是林立宇干我打错XD 01/25 19:45
18F：→ TMDTMD2487: 而且表格是正三角形的XD 01/25 19:46
19F：推 ahahahahah: 我好像只会洪逸的算法欸==一直觉得演算法那个很不直观 01/25 20:08
20F：→ ahahahahah: ，这样ok吗？ 01/25 20:08
21F：→ TMDTMD2487: 好吧 其实没关系啦 搞清楚为什麽algo跟ds有什麽差就好 01/25 20:14
22F：→ TMDTMD2487: 然後用你喜欢的算法就好了 01/25 20:14
23F：推 sarsman: 我也是用林立宇的方法算xd，觉得视觉上比较好记忆 01/25 22:38
24F：推 gary70812: 原本也是用洪逸的算法，直到遇到10个点的BST..... 01/25 23:05
25F：推 pp891190007: 那可不可以教一下怎麽林立宇算法？哈哈哈以为业配 01/26 00:39
26F：推 winiel559: 林立宇算法好像就是枫叶本算法 01/26 00:42
27F：→ winiel559: 去找原文书xdd 01/26 00:43
28F：→ winiel559: obst超烦的，有够难算，但是又会考全套= = 01/26 00:44
29F：→ TMDTMD2487: 其实算法没什麽差 只是他的那个表格我觉得很乾净 01/26 01:02
30F：→ TMDTMD2487: 他只是把表格化成三个cost/weight/root 01/26 01:03
31F：→ TMDTMD2487: 然後他定义的cost(i,j)那个ij我觉得比较直觉 01/26 01:03
32F：→ TMDTMD2487: 我记得洪逸的定义cost(i,j)好像是不包含i还是j的OBST 01/26 01:04
33F：→ TMDTMD2487: 我看过的DP的运算 算起来都有一个规律其实就算七八个 01/26 01:06
34F：→ TMDTMD2487: 点的obst 算起来大概也是十分钟以内就可以完成 01/26 01:07
36F：→ TMDTMD2487: 我也是先看洪逸的那个表格看到觉得很痛苦这个舒服多XD 01/26 01:10
37F：推 pp891190007: 楼上在洗三温暖 （别理我 01/26 10:34
38F：推 pp891190007: 是说~T大你的算法好像就是algo算法 只是摆横的 无意 01/26 10:37
39F：→ pp891190007: 冒犯 01/26 10:37
40F：推 winiel559: 是啊，林立宇算法就是algo算法 01/26 10:55
41F：推 TMDTMD2487: 我觉得这一横摆算起来的感受就有差啦XD 01/26 11:31
42F：→ aggress5566: 我觉得DS跟演算法有重叠的部分还是以演算法为主 DS 01/26 11:54
43F：→ aggress5566: 原文圣经那本本来就很… 01/26 11:54
44F：推 winiel559: 我也不太喜欢Horowitz那本 01/26 12:22
45F：推 TMDTMD2487: 我刚刚想说很久没算obst算一下成大那题 11分钟 真他 01/26 14:05
46F：→ TMDTMD2487: 妈垃圾题目 01/26 14:05
47F：推 TMDTMD2487: 我是看algo之後才看出这个dp算式的规律是啥的 01/26 14:07
48F：推 pp891190007: 怎麽噜？不就用演算法写而已吗？ 01/26 14:45
49F：推 TMDTMD2487: 没啊成大去年考一个七个点的真的算到很烦XD 01/26 19:37
50F：推 winiel559: n^3 手算很想死啊 01/26 20:13
51F：推 pp891190007: 没事没事 分数拿到 就一生平安！ 01/27 00:13