部分恕删，另外在这边告知一下原po 我在我这篇标题有鸡婆加上学校年份，以供未来有需要的人也可以搜到 还请原po见谅 ※ 引述《leexu3 (LEE)》之铭言： : 成大的99年Checkboard : https://imgur.com/a/rLdeR : 1.写不出code 虽然感觉很明显对 ＝＝ 不知道这样写pseudo code可不可以： // size: 记录大小为2^n * 2^n之checkerboard的n function board_cover(board bd, size n): // 若只剩大小为2 * 2之checkerboard， // 根据我们的做法，必定当中已有1 * 1的square不可cover， // 等同被移除一块square if size == 1: 将一个tromino覆盖剩余区域; return; else: 将大小为2^n * 2^n之checkerboard划分为4块大小为2^n-1 * 2^n-1的board; 分别标记为b1, b2, b3, b4; 判断该4块中哪块board有存在1 square不可cover; 在2^n * 2^n之board的中心覆盖上一个tromino，其覆盖的区域各有1 square位在 其它「原不存在不可cover的1 square」的3大块board; // 如此一来，此时4大块2^n-1 * 2^n-1的board各有1 square不可cover // 递回对这4大块board再去填满tromino board_cover(b1, n - 1); board_cover(b2, n - 1); board_cover(b3, n - 1); board_cover(b4, n - 1); return; 我觉得应该这样大概写出做法就可以了，可以的话再画图示意， 这样阅卷老师应该会接受吧QwQ？ 资料结构还有其他细节小弟我觉得应该不算此题重点，所以就没详述了 （用array存board、中心的index、如何判断哪一块存在不可cover的square） 若概念有问题或哪边还可以写得更不冗长，还请各位不吝指点，感谢！ : 成大103 : https://imgur.com/a/iFpp4 : Prove that "the longest increasing subsequence problem" can be reduced : to "the edit distance problem" : 两个演算法我会 但不知道怎麽reduced 感觉就是有读没有通 : 想上来请益各位 谢谢！ 不好意思这题最後的细节我也不清楚 （有了min cost的编辑序列，该如何用这序列去求出LCS，也就是LIS）， 以下前段主要来自於林立宇老师的演算法讲义 假设LIS中input sequence为X = (7, 4, 1, 2, 6) 对X排序，可得sequence Y = (1, 2, 4, 6, 7)，则求LIS(X)又等同求LCS(X, Y) 再来看Edit distance problem(ED) 定义edit operation及其cost： 1. substitution，Cs = 2 2. insertion，Ci = 1 3. deletion，Cd = 1 题外话，我觉得「替代」的操作在此题reduce中似乎没用到？（概念有错还请指正） 接着是min edit cost与LCS length的关系 首先LIS(X) = LCS(X, Y) = (1, 2, 6) 假设为ED(X, Y)为要将X编辑成Y的min cost， 等同於在X中delete非LIS的元素（删x1, x2的7, 4），接着同时对照Y 在X对应的位置insert被删掉的元素（在2, 6间插4、在最尾端插7） 由上述例子可知，假设X的元素数量（|X|）为n，LCS元素数为|LCS(X, Y)| 则ED(X, Y) = 2 * (|X| - |LCS(X, Y)|) 所以当若给一input sequence X（也同样是欲求LIS的X）， 排序X得Y，接着先找出具有min cost的编辑序列， 再来我不太理解的是，该如何从这些insert、delete的operation中， 求出X和Y的LCS，也就是X的LIS呢？ 林立宇老师的讲义上只写「欲求LIS(X)」，只需在过程中额外记录一些编辑的程序即可 假设X = (4, 1, 2)，Y = (1, 2, 4) min cost of edit sequence是从X删除x1，插入y3到X， 那我们该如何从这两个operation中，得知X的LIS就是(x2, x3)，也就是1, 2呢？ 小弟的猜想是，最後的编辑序列求出後， 「只执行」编辑序列中delete的操作，一旦编辑序列中没有delete，就output X的内容 值得一提的是，将substitution 视为等同 delete 再 insert，所以成本我设为相同 （2 = 1 + 1） 当最後有了编辑序列後，我将每个substitution都以「delete + insert」的操作取代 或者，一开始直接将substitution的cost设为无限大， 如此一来必不会有substitution的操作出现，即可正确输出 （感谢FARXIS大耐心提出反例与盲点） 以上是我查过资料後的一些想法，还请大家有其他想法尽量提出、指正， 感谢！ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.26.141.161 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1515147047.A.89D.html 感谢F大提出一个我很大的盲点，确实这样就说是min cost实在不显然且不严谨 立宇老师讲义上似乎也没有提到这部分，我再思考看看 原来如此！因为我是看到题目中，Output一个是edit operation的sequence 一个是longest sequence of positions，所以才想说是不是optimization problem 那我改成 「只执行」编辑序列中delete的操作，一旦编辑序列中没有delete，就output X的内容 如此一来，尽管input X是sorted，当要输出时一开始判断也会因X没有delete就Output 请问F大这样可以吗？ 感谢F大耐心看我的想法并挑出许多瑕疵QwQ 对耶！ 那请问F大，因为 我将substitution 视为等同 delete 再 insert，所以成本我设为相同 （2 = 1 + 1） 所以为了让我能以上述建构解的方法正确运作， 当最後有了编辑序列後，我将每个substitution都以「delete + insert」的操作取代 或者，我将substitution的cost设为无限大，如此一来必不会有substitution的操作出现 那请问建构解的部分这样是否就可行了呢？ 另外我google了几篇有提到这两者间转换的文章，似乎都没说明到为何可以是min cost 请问F大方便提点一下吗？ ※ 编辑: ShenJing (114.26.141.161), 01/06/2018 00:24:12 原来如此！非常感谢F大！ ※ 编辑: ShenJing (114.26.141.161), 01/06/2018 07:39:27