題目：http://poj.org/problem?id=1163
從三角塔最頂端走、每次可以走左或走右，讓路線上數字總和最高
是IOI1994年的題目
和pku3176題意一模一樣，只不過是USACO2005銅組、範圍到350
程式碼：http://codepad.org/y7XYV0Pi
撇開三角形對新手比較容易出錯的話，是很簡單的DP
對於每一個位置，不是從左上過來、就是從右上過來(如果存在的話)
所以該位置可能的最高權重，就是左上或右上的最大可能選一個大的
其餘請參考代碼、記得要判邊界(我比較偷懶直接初始化0啦)
沒有留言:
張貼留言