|
|
|
|
背景 Background |
|
|
|
Due to the talent of talent123,当talent123做完NOIP考了两次的二取方格数和vijos中的三取方格数后，突发奇想....
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
在一个宽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的情况！！！ |
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
第一行：三个整数：n M N
以下的N行每行M个数字，代表你要处理的矩阵。
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
只有一行：你所取得的数字的和。 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
共有10个测试数据，每个测试数据包含1个测试点，每个测试点的时间限制为2秒钟。 |
|
|
|
|
|
|
|
来源 Source |
|
|
|
本题目来自：北京市，中关村中学，高三9班，孙一（网名:talent123）,联系方式：865383864（QQ） |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1653 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
