A25812. 猴子摘桃子
题目描述
猴子摘桃子
题目描述
果园有M行N列套数，每棵书上有一定数量的桃子。猴子从左上角的桃树开始进入果园摘桃子，每到一个桃树下都会将树上的桃子摘完，但猴子每次只能移动到当前所在桃树的下边或右边的桃树下摘桃子，照这个移动方案，猴子在果园中最多可以摘到多少桃子。
现给出M和N的值，以及每棵桃树上的桃子数量，照移动方案，计算出猴子在果园最多可以摘到多少桃子。
例如：M=2 ,N=3
桃子数量为
2 3 1
1 4 2
这种情况下，为了摘到最多的桃子，猴子摘桃子的顺序应为2，3，4，2，总桃子数为11。
输入描述
第一行输入正整数 M和N，分别代表行数和列数 。
之后输入M行N列每课桃树上的桃子数量。
输出描述
一个正整数，代表猴子按移动规则在果园中最多可以摘到多少桃子。
输入样例
2 3
2 3 1
1 4 2输出样例
11参考答案
#include <iostream>
using namespace std;
int dp[21][21];
int a[21][21];
int m, n;
int main() {
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] += max(a[i][j - 1], a[i - 1][j]);
}
}
cout << a[m][n];
return 0;
}答案解析
// 答案2
#include <bits/stdc++.h>
using namespace std;
long long a[1000][1000], b[1000][1000];
// 数组a用来存储每棵树上桃子数量，数组b用来存储每条路线上每个点最多拿到的桃子数量
int main() {
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
b[i][j] = a[i][j] + max(b[i - 1][j], b[i][j - 1]);
// 每个点上最多的桃子数量为这棵树上的桃子加上左边或上边树上累积的较多桃子数
/* 如数组a是 ，那么数组b就是
3 1 99 3 4 103
10 1 1 13 14 104
10 1 1 23 24 105
*/
cout << b[m][n];
return 0;
}