/ Vijos / 题库 /

疯狂的方格取数

疯狂的方格取数

背景

Due to the talent of talent123,当talent123做完NOIP考了两次的二取方格数和vijos中的三取方格数后,突发奇想....

描述

在一个宽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个数字,代表你要处理的矩阵。

输出格式

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

样例1

样例输入1

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

样例输出1

265

限制

共有10个测试数据,每个测试数据包含1个测试点,每个测试点的时间限制为2秒钟。

来源

本题目来自:北京市,中关村中学,高三9班,孙一(网名:talent123),联系方式:865383864(QQ)

信息

ID
1653
难度
5
分类
图结构 | 网络流动态规划 点击显示
标签
递交数
424
已通过
139
通过率
33%
被复制
7
上传者

相关

在下列训练计划中:

RP++分类题库