网站关键词搜不到了,2022年互联网公司排名,php网站导航,wordpress get footer1022: 淘金 时间限制: 1 Sec 内存限制: 128 MB提交: 205 解决: 75[提交] [状态] [讨论版] [命题人:外部导入]题目描述 在一片n*m的土地上#xff0c;每一块1*1的区域里都有一定数量的金子。这一天#xff0c;你到这里来淘金#xff0c;然而当地人告诉你#xff0c;如果你… 1022: 淘金 时间限制: 1 Sec 内存限制: 128 MB提交: 205 解决: 75[提交] [状态] [讨论版] [命题人:外部导入] 题目描述 在一片n*m的土地上每一块1*1的区域里都有一定数量的金子。这一天你到这里来淘金然而当地人告诉你如果你挖了某一区域的金子上一行下一行左边右边的金子你都不能被允许挖了。那么问题来了你最多能淘金多少 输入 对于每组数据第一行两个数n,m表示土地的长和宽(1n,m200) 接下来n行,每行m个数表示每个区域的金子数量每个区域的金子数量不超过1000 输出 对于每组数据输出最多得到的金子数量 样例输入 4 6
11 0 7 5 13 9
78 4 81 6 22 4
1 40 9 34 16 10
11 22 0 33 39 6 样例输出 242 来源/分类 2017年中南大学研究生复试机试题 1 #includeiostream2 #includecmath3 using namespace std;4 /*典型的动态规划题目其实这道题可以拆开来看行和列先对每一行做动态规划可以5 得出这一行能够挖到的最大数量的金币然后用一个数组把每一行的最大值记录下来再6 对这个数组进行动态规划两次的规则是一样的*/7 int distcol[205];//行记录8 int distrol[205];//列记录9 int result[205];//结果记录
10 int gold[205][205];
11 int max(int a, int b){
12 if (a b)return a;
13 return b;
14 }
15 int main(){
16 int n, m;
17 while (cinnm){
18 for (int i 0; i n; i){
19 for (int j 0; j m; j){
20 cin gold[i][j];
21 }
22 }
23 for (int i 0; i n; i){
24 distcol[0] gold[i][0];
25 distcol[1] max(gold[i][0], gold[i][1]);
26 for (int j 2; j m; j){//判断这个位置到底挖不挖
27 distcol[j] max(distcol[j - 1], distcol[j - 2] gold[i][j]);
28 }
29 distrol[i] distcol[m-1];
30 }
31 result[0] distrol[0];
32 result[1] max(distrol[0], distrol[1]);
33 for (int i 2; i n; i){//判断这一行到底挖不挖
34 result[i] max(result[i - 1], result[i - 2] distrol[i]);
35 }
36 cout result[n - 1] endl;
37
38 }
39 return 0;
40 } 转载于:https://www.cnblogs.com/tangyimin/p/10578406.html
