2125: 宝典2第十一章方格取数

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:23 Solved:22

Description

【题目描述】方格取数(GetNum.cpp/c/pas) NOIP 2000

张琪曼:“哇,想不到墨家宝库中还有这么多魔法石。”

李旭琳:“但是看上去好像要按照规则取魔法石才行,否则会发生危险的。”

简而言之就是有n×n的方格数(n≤8),其中的某些方格中填入正整数表示该方格中的魔法石数量,而其他的方格中则放入数字0,表示该方格中没有魔法石。如图所示:

现从左上角出发,可以向下行走也可以向右走,直到到达右下角,在走过的路上,他可以取走方格中的数,取走的方格数将变为0,张琪曼和李旭琳各走一次,试找出两条这样的路径,使得取得的数之和最大。

【输入格式】

  输入的第一行为一个整数n,表示n×n的方格图,接下来每行有三个整数,前两个表示位置,第三个数为该位置上的数。一行单独的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

加入题单

上一题 下一题 算法标签: