1698: 最长路径
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：9
解决：8
题目描述
有一个N*N的棋盘，棋盘上每个格子里有一个数字。小明从棋盘的左上角（0,0）位置开始出发，要走到右下角的出口。小明每次只能向右或向下走，不可以向其他方向走。小明要怎么走才能使得他走过的路径上的数字之和最大？请你输出这个最大的和。
例如：下面是5*5的棋盘
|
2 |
4 |
6 |
8 |
10 |
|
10 |
8 |
5 |
4 |
6 |
|
4 |
8 |
9 |
2 |
1 |
|
4 |
7 |
9 |
3 |
4 |
|
1 |
5 |
4 |
2 |
6 |
则小明沿着黄色的路径走会得到路径上的数字最大。
输入
输入有若干组。每组第一行是1个正整数N，表示棋盘的大小。随后有N行，每行有N个正整数，表示每个格子上的数字。
输出
输出路径上的数字的最大和。
样例输入 复制
5
2 4 6 8 10
10 8 5 4 6
4 8 9 2 1
4 7 9 3 4
1 5 4 2 6
6
2 4 6 8 10 12
10 8 5 4 6 13
4 8 9 2 1 12
4 7 9 3 4 16
1 5 4 2 6 15
1 5 4 2 6 15样例输出 复制
59
113