1424: VIJOS-P1653

在一个宽M，长N的矩阵中，请你编一个程序，n次从矩阵的左上角走到矩阵的右下角，每到一处，就取走该处的数字，请你选择一 种走法使取得的数字的和最大,并输出其最大值。其中：3< =M< =20      M< =N< =100      1< =n< =10    如输入数据： 3  10  13    0  1  2  3  4  9  7  1  3  1 9  1  2  2  3  6  7  8  1  2 1  2  3  4  5  9  8  7  6  1 9  7  1  3  1  9  1  2  2  3 6  7  8  1  2  1  2  3  4  5 9  1  2  2  3  6  7  8  1  2 1  2  3  4  5  9  8  7  6  1 9  7  1  3  1  9  1  2  2  3 6  7  8  1  2  1  2  3  4  5 9  1  2  2  3  6  7  8  1  2 1  2  3  4  5  9  8  7  6  1 9  7  1  3  1  9  1  2  2  3 6  7  8  1  2  1  2  3  4  0 其中n=3         M=10         N=13 即当n=3时，就相当于是3取方格数。 对于以上的数据： 将输出：297 //注：如过你想到了无记忆性搜所的方法（不管你怎样优化），你可以直接放弃这道题了。 //提示1：动态规划如果用的是二位数组，规模为100*100000即可。 //提示2：如果你坚信自己的程序已经无可优化了，可有2个数据依然超时，那么告诉你，存在数据有M< n的情况！！！

第一行：三个整数：n  M  N 以下的N行每行M个数字，代表你要处理的矩阵。

只有一行：你所取得的数字的和。

4 6 7
0 2 3 4 5 6
6 5 4 3 2 1
0 9 8 7 6 5
12 3 4 5 6 7
0 0 0 1 2 3
12 23 34 45 1 23
4 5 6 6 1 0

265