#4672. 猴子摘桃子(2022年3月STEMA选拔赛)
猴子摘桃子(2022年3月STEMA选拔赛)
Background
猴子摘桃子
题目描述:
果园有M行N列桃树,每棵桃树上有一定数量的桃子。猴子从左上角的桃树开始进入果园摘桃子,每到达一棵桃树下都会将树上的桃子摘完,但猴子每次只能移动到当前所在桃树的下边或右边的桃树下摘桃子,按照这样的移动方案,猴子在果园中最多可以摘到多少桃子。
现给出M和N的值,及每棵桃树上的桃子数量,按照移动方案,计算出猴子在果园最多可以摘到多少桃子。
例如:
M=2,N=3
桃子数量为
2 3 1
1 4 2
这种情况下,为了摘到最多数量的桃子,猴子摘桃子的顺序应为2,3,4,2,总桃子数为11.
输入描述:第一行输入两个正整数M,N(1≤M≤20,1≤N≤20),M表示果园桃树的行数;N表示果园桃树的列数;两个正整数之间一个空格隔开
第二行开始输入M行数据,每行N个正整数(1≤正整数≤1000),正整数表示每棵桃树上的桃子数量,正整数之间一个空格隔开
输出描述:输出一个整数,表示猴子在果园中最多可以摘到多少桃子
样例输入:2 3
1 4 5
5 4 6
样例输出:16
评分标准:
7分:能正确输出一组数据;
7分:能正确输出两组数据;
8分:能正确输出三组数据;
8分:能正确输出四组数据。
Limitation
1s, 1024KiB for each test case.