作者bc5678 ( )
看板C_and_CPP
标题[ACM ][TLE] 838 Worm World
时间Sat Sep 19 22:14:19 2009
UVa 838 Worm World
原文题目网址
http://online-judge.uva.es/p/v8/838.html
中文题目网址, 看图就能很明白知道题目在问什麽了
http://www.tcgs.tc.edu.tw/~sagit/luckycat/q838.htm
题目大意:
给定 N*N 方阵 (0 < N <= 12), 方阵里面的数字介於0~1000,
在路径只能左右移动或上下移动的条件下, 找出拥有不重复数字的最长路径之长度
/***** Sample Input *****/
2
3
1 2 1
2 3 4
3 2 1
8
6 8 18 15 24 20 2 20
6 2 15 2 17 15 3 7
0 11 18 16 20 15 1 11
6 2 6 13 4 17 20 16
5 12 7 2 3 5 18 23
7 13 3 2 2 11 4 23
16 23 10 2 4 12 5 20
17 12 10 1 13 12 6 20
/***** Sample Output *****/
4
20
==========
我自己的方法是针对每一位置N(x, y)做brute forth搜寻
搜寻的深度不会超过M (M = min(数字种类, 方阵大小) )
找到之後就将此路径记下, 以後有其他位置起始的路径要通过时就拿来reuse
如果找到的路径长度已经等於M, 那自然就是直接回传答案
对於上面两个测资是没问题, 但是跑自己做的一个测资时就变得极慢
1
12
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80 81 82 83
84 85 86 87 88 89 90 91 92 93 94 95
96 97 98 99 100 101 102 103 104 105 106 107
108 109 110 111 112 113 114 115 116 117 118 119
120 121 122 123 124 125 126 127 128 129 129 129
132 133 134 135 136 137 138 139 140 129 142 143
因为光是从N(0, 0)出发时brute forth所产生的路径就太多了
不知是否有人有想出更好的方法或是更好的终止条件?
补上TLE的code :
http://codepad.org/KOyonZNk
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 112.104.27.222
1F：推 goliathplus:用 DP 解 09/19 22:33
2F：→ bc5678:应该没办法单纯地切sub problem吧, 愿闻其详? 09/19 22:38
3F：→ takingblue:backtracking 09/19 23:52
Lucky猫的提示也是这个, 不过不知详细怎麽做呢?
http://203.64.52.212/~ACM/
※ 编辑: bc5678 来自: 123.204.164.164 (09/21 00:55)
4F：推 cutecpu:65 ~ 72 行 的 reuse 拿掉，直接跑 74 ~ 77 行的递回 09/21 17:03
5F：→ cutecpu:127 行 改成 if(n) printf("\n"); 09/21 17:03
6F：→ bc5678:问题已解决, 感谢热心的CPU 09/21 19:18
7F：推 DJWS:想请教一楼所说的DP解的详细内容，谢谢。 :) 09/22 09:22