[ACM ] 10318

看板C_and_CPP作者 (Xen)時間14年前 (2010/05/26 21:32), 編輯推噓0(0推 0噓 7→)
留言7則, 3人參與, 最新討論串1/1
題號： 10318 遇到的問題： 嗯.....Branch & Bound還是TLE 有問題的code： (請善用置底文的標色功能) http://gist.github.com/414487 補充說明： 基本上這題不用考慮按的順序 所以把2^25種按法都求出來取按最少次的為答案 我想到能cut的條件只有兩個 1.按的次數大於目前解按的次數 2.已經按到第k行時第k-2行還有沒亮的燈 但是這兩種cut條件好像不夠? 如果case是5*5的面板而且沒有答案他還是會跑完2^25種 最後一定TLE 但是這題確定是可以用Branch & Bound解的 請問有沒有高人替小弟解答一下 ※ 編輯: fasthall 來自: 140.114.86.66 (05/26 21:37)
→
05/26 23:42, , 1F
pow[25] = 33554432; 這個好像超出陣列pow的範圍了
05/26 23:42, 1F
→
05/27 00:49, , 2F
從左上角開始照row major按的話,第二個bound可以再加速
05/27 00:49, 2F
→
05/27 00:51, , 3F
例如按到[2][2]時, [1][1]其實就已經不會變了
05/27 00:51, 3F
→
05/27 00:51, , 4F
不過應該不差這麼一點@@ 這兩個條件應該夠了才對
05/27 00:51, 4F
→
05/27 00:56, , 5F
depends on pattern
05/27 00:56, 5F
→
05/27 09:52, , 6F
嗯......用DFS就可以過了
05/27 09:52, 6F
→
05/29 06:20, , 7F
不然你原本用什麼XDDD
05/29 06:20, 7F
‣ 更多 fasthall 的文章
文章代碼(AID): #1B_IBiBI (C_and_CPP)