PKU 1080 Human Gene Functions
摘要: 每一步求出當(dāng)前最佳狀態(tài)。之后的每一步就可以根據(jù)前一步的結(jié)果計(jì)算出最佳狀態(tài)。不過前提是兩個(gè)狀態(tài)都是具有相同最優(yōu)子問題。
對每一個(gè)問題，可先降低問題的難度，例如將問題的數(shù)據(jù)簡化。然后考慮每個(gè)問題的確切條件，根據(jù)條件思考用什么最好的結(jié)構(gòu)來存取狀態(tài)。
閱讀全文
PKU 1953 World Cup Noise
摘要: 如果尾數(shù)是0，則倒數(shù)第二位可以是1或0，有f(n-1)種；如果尾數(shù)是1，則倒數(shù)第二位只能是0倒數(shù)第三位可是0或1，有f(n-2)種。所以f(n) = f(n-1) + f(n-2)。
閱讀全文
PKU 1321 The Alphabet Game
摘要: 本題要求對所有的字母，可以用直線將它們都分開，使被分開的每個(gè)格子只包含同樣的字母或是沒有字母。解法：對所給字母劃分最小區(qū)域。然后兩兩處理，對任意的兩個(gè)方塊區(qū)域，只要有一條直線穿過即可。這樣有兩種可能。橫穿或豎穿或兩者都有，但只考慮橫穿或是豎穿就可以了。如果能橫穿，則枚舉所有可能的橫穿線，看看是存在一條橫穿線不會(huì)穿過其他方塊。如果有，則處理別的區(qū)域，直到所有的區(qū)域都滿足要求就是YES。如果不存在，考慮豎穿，處理方法跟橫穿一樣的。如果豎穿也不行，表示NO；如果行，就處理其他區(qū)域。
閱讀全文
pku 1321
摘要: 因?yàn)槿我鈨蓚€(gè)點(diǎn)不同行同列，所以對行，每行之存一個(gè)點(diǎn)；對列，用T:array[i]標(biāo)記第i列是否已被存過即可。
閱讀全文
PKU 2253 Frogger
摘要: POJ2253 Frogger：該題要求男娃跳到女娃所經(jīng)過的最短路程中的最大邊。還是Floyd算法。因?yàn)榍嗤芴S范圍有限，想從i經(jīng)過k個(gè)節(jié)點(diǎn)到達(dá)j，則i到j(luò)中的每段路徑k到k+1都必須在跳躍范圍內(nèi)。所以要找出另外一條i到j(luò)新路徑中的最大跳，然后與當(dāng)前已算出的i到j(luò)的最大跳比較。默認(rèn)為較小的蛙才跳的過去。這里用Floyd求解。
閱讀全文
PKU 2243 Knight Moves
摘要: 輸入兩個(gè)點(diǎn)的位置，用(a-h) 表示列，用(1-8) 表示行。第一個(gè)為起點(diǎn)，第二個(gè)為終點(diǎn)，要求計(jì)算從起點(diǎn)到終點(diǎn)最少走幾步。用廣度優(yōu)先搜索，可以較快的的達(dá)到目的，因?yàn)閺V搜按層遍歷。有利于迅速查找最短路徑。
閱讀全文
PKU 2240 Arbitrage
摘要: 運(yùn)用Floyd算法，在一個(gè)矩陣中，對于i和j之間的權(quán)值，如果有i和j之間的某個(gè)節(jié)點(diǎn)k，使得w[i, k] + w[k, j] 比w[i, j]更符合要求，則使w[i, j] = w[i, k] + w[k, j]。
閱讀全文
PKU2244
摘要: 對于所給的數(shù)目，求出讓2 最后被刪除的最小刪除間隔h。每組數(shù)據(jù)都從第一個(gè)開始刪起，然后以間隔為h，繼續(xù)刪除其它數(shù)。
閱讀全文