首页 > 代码库 > POJ 2948 Martian Mining（DP）
POJ 2948 Martian Mining（DP）
题目链接
题意 ： n×m的矩阵，每个格子中有两种矿石，第一种矿石的的收集站在最北，第二种矿石的收集站在最西，需要在格子上安装南向北的或东向西的传送带，但是每个格子中只能装一种传送带，求最多能采多少矿。
思路 ：记忆化搜索。也可以用递推。
//2948#include <stdio.h>#include <string.h>#include <iostream>using namespace std ;int yeye[510][510] ,blog[510][510] ;int dp[510][510] ;int DP(int row,int col){ if(row < 0 || col < 0) return 0 ; else if(dp[row][col] != -1) return dp[row][col] ; else return dp[row][col] = max(DP(row-1,col)+yeye[row][col],DP(row,col-1)+blog[row][col]) ;}int main(){ int n, m ; while(~scanf("%d %d",&n,&m)) { if(n == 0 && m == 0) break ; for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ;j++) scanf("%d",&yeye[i][j]) ; for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ;j++) scanf("%d",&blog[i][j]) ; memset(dp,-1,sizeof(dp)) ; for(int i = 0 ; i < n ; i++) for(int j = 1 ; j < m ; j++) yeye[i][j] += yeye[i][j-1] ; for(int i = 0 ; i < m ; i++) for(int j = 1 ; j < n ; j++) blog[j][i] += blog[j-1][i] ; printf("%d\n",DP(n,m)) ; } return 0 ;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。