重庆网站设计案例,大学生创新创业大赛获奖名单,wordpress邮件联系,中国建设银行北京分行门户网站公告题目 淘金
题目描述 在一片n*m的土地上#xff0c;每一块1*1的区域里都有一定数量的金子。这一天#xff0c;你到这里来淘金#xff0c;然而当地人告诉你#xff0c;如果你要挖(x, y)区域的金子#xff0c;就不能挖(x-1#xff0c;y),(x1, y)以及横坐标为y-1和y1的金…题目 淘金
题目描述 在一片n*m的土地上每一块1*1的区域里都有一定数量的金子。这一天你到这里来淘金然而当地人告诉你如果你要挖(x, y)区域的金子就不能挖(x-1y),(x1, y)以及横坐标为y-1和y1的金子(也就是说你挖了某一区域的金子上一行下一行左边右边的金子你都不能被允许挖了)。那么问题来了你最多能淘金多少 数据输入 对于每组数据第一行两个数n,m表示土地的长和宽(1n,m200) 接下来n行,每行m个数表示每个区域的金子数量每个区域的金子数量不超过1000 结果输出 对于每组数据输出最多得到的金子数量。 a[i]记录某一行第i块金子的数目。
思路这个题可以采取动态规划的思想。挖了某一块的金子就无法挖这块金子上一行下一行左边与右边的金子。
那么可以考虑一个简化的淘金假设只有一行那么如果你挖了a[i],你就没有办法挖a[i-1]与a[i1]。假设d[i]代表截止挖到这一行第i块金子我已经得到的最大金子数量那么d[总共列数]就是这一行最大能挖到的金子数量。d[i] max{d[i-2]d[i-3]}a[i];
最后每一行能够得到的最大金子数都为d[最大列数]。然后我们对d[i][最大列数]进行列举递推方程式。
k[i][最大列数]代表截止到第i行为止能获得的最大的金子数
k[i][最大列数]max{k[i-2][最大列数],k[i-3][最大列数]}d[i]
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn 200 10;
int a[maxn][maxn]; // 区域金子量
int b[maxn]; // 考虑某一行b[i]表示[0, i]这个区域中并且选择了i个金子能得到最大值// b[i] max(b[i-2], b[i-3])a[i]
int c[maxn]; // c[i]表示第i行能得到的最多金子数量
int d[maxn]; // d[i]表示考虑[0,i]行选择了第i行能得到最多金子
int main(){int n, m;while(scanf(%d%d, n, m)2) {for(int i0; in; i) {for(int j0; jm; j) scanf(%d, a[i][j]);}for(int i0; in; i) {for(int j0; jm; j) {b[j] max(j-20?b[j-2]:0, j-30?b[j-3]:0) a[i][j];}c[i] max(b[m-1], m-20?b[m-2]:0); // 第i行能得到的最多金子数量 d[i] max(i-20?d[i-2]:0, i-30?d[i-3]:0) c[i];}printf(%d\n, max(d[n-1], n-20?d[n-2]:0));}return 0;
}
