Preparing NOJ
机器人Rob在一个有n*n个方格的方形区域F 中收集样本。(i,j)方格中样本的价值为v(i,j),如下图所示。
Rob从方形区域F的左上角A点出发,向下或向右行走,直到右下角的B点,在走过的路上,收集方格中的样本。Rob从A点到B 点共走2次,试找出Rob的2条行走路径,使其取得的样本总价值最大。
给定方形区域F中的样本分布,编程计算Rob的2条行走路径,使其取得的样本总价值最大。
输入第1行有1个正整数n,表示方形区域F有n*n个方格。接下来每行有3个整数,前2个表示方格位置,第3个数为该位置样本价值。最后一行是3个0。
输出计算的最大样本总价值。
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
67
undefined
本题由旧版NOJ导入,来源:算法设计与实验题解