http://acm.pku.edu.cn/JudgeOnline/problem?id=1767Which is Next 二叉樹(shù),好煩的題,要考慮好多情況。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3333Co-workers from Hell搜索過(guò)的。
一開(kāi)始沒(méi)有想到用搜索做,因?yàn)闋顟B(tài)有2^100之多,一直以為有多項(xiàng)式算法。
后來(lái)問(wèn)幾個(gè)人都是搜的,才敢去做,結(jié)果0ms就過(guò)了。
兩個(gè)剪枝:
1、跳向前的邊,如果長(zhǎng)度不如一步一步向前走那么長(zhǎng),那肯定不走。
2、往后跳的邊,肯定走。
關(guān)于這個(gè)題,之前我還想把它
轉(zhuǎn)換成最長(zhǎng)路問(wèn)題(每條邊只走允許一次),后來(lái)還是發(fā)現(xiàn)不能轉(zhuǎn)換。況且,就算轉(zhuǎn)換成了每條邊只允許走一次的最長(zhǎng)路問(wèn)題,我也不知道有什么好的算法,bellman-ford可以求最長(zhǎng)路,但前提是無(wú)正環(huán)。
posted on 2007-08-17 11:47
LSM 閱讀(594)
評(píng)論(5) 編輯 收藏 引用 所屬分類(lèi):
其他