PKU 1080 Human Gene Functions
摘要: 每一步求出当前最佳状态。之后的每一步就可以根据前一步的结果计算出最佳状态。不过前提是两个状态都是具有相同最优子问题。
对每一个问题，可先降低问题的难度，例如将问题的数据简化。然后考虑每个问题的确切条件，根据条件思考用什么最好的结构来存取状态。
阅读全文
PKU 1953 World Cup Noise
摘要: 如果尾数是0，则倒数第二位可以是1或0，有f(n-1)种；如果尾数是1，则倒数第二位只能是0倒数第三位可是0或1，有f(n-2)种。所以f(n) = f(n-1) + f(n-2)。
阅读全文
PKU 1321 The Alphabet Game
摘要: 本题要求对所有的字母，可以用直线将它们都分开，使被分开的每个格子只包含同样的字母或是没有字母。解法：对所给字母划分最小区域。然后两两处理，对任意的两个方块区域，只要有一条直线穿过即可。这样有两种可能。横穿或竖穿或两者都有，但只考虑横穿或是竖穿就可以了。如果能横穿，则枚举所有可能的横穿线，看看是存在一条横穿线不会穿过其他方块。如果有，则处理别的区域，直到所有的区域都满足要求就是YES。如果不存在，考虑竖穿，处理方法跟横穿一样的。如果竖穿也不行，表示NO；如果行，就处理其他区域。
阅读全文
pku 1321
摘要: 因为任意两个点不同行同列，所以对行，每行之存一个点；对列，用T:array[i]标记第i列是否已被存过即可。
阅读全文
PKU 2253 Frogger
摘要: POJ2253 Frogger：该题要求男娃跳到女娃所经过的最短路程中的最大边。还是Floyd算法。因为青蛙跳跃范围有限，想从i经过k个节点到达j，则i到j中的每段路径k到k+1都必须在跳跃范围内。所以要找出另外一条i到j新路径中的最大跳，然后与当前已算出的i到j的最大跳比较。默认为较小的蛙才跳的过去。这里用Floyd求解。
阅读全文
PKU 2243 Knight Moves
摘要: 输入两个点的位置，用(a-h) 表示列，用(1-8) 表示行。第一个为起点，第二个为终点，要求计算从起点到终点最少走几步。用广度优先搜索，可以较快的的达到目的，因为广搜按层遍历。有利于迅速查找最短路径。
阅读全文
PKU 2240 Arbitrage
摘要: 运用Floyd算法，在一个矩阵中，对于i和j之间的权值，如果有i和j之间的某个节点k，使得w[i, k] + w[k, j] 比w[i, j]更符合要求，则使w[i, j] = w[i, k] + w[k, j]。
阅读全文
PKU2244
摘要: 对于所给的数目，求出让2 最后被删除的最小删除间隔h。每组数据都从第一个开始删起，然后以间隔为h，继续删除其它数。
阅读全文