Preparing NOJ

收集样本问题

1000ms 65536K

Description:

机器人Rob在一个有n*n个方格的方形区域F 中收集样本。(i,j)方格中样本的价值为v(i,j),如下图所示。

Rob从方形区域F的左上角A点出发,向下或向右行走,直到右下角的B点,在走过的路上,收集方格中的样本。RobA点到B 点共走2次,试找出Rob2条行走路径,使其取得的样本总价值最大。

给定方形区域F中的样本分布,编程计算Rob2条行走路径,使其取得的样本总价值最大。

Input:

输入第1行有1个正整数n,表示方形区域Fn*n个方格。接下来每行有3个整数,前2个表示方格位置,第3个数为该位置样本价值。最后一行是30

Output:

输出计算的最大样本总价值。

Sample Input:

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

Sample Output:

67

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1237

Tags

Submitted 4

Passed 2

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet