首页 > 代码库 > POJ 2948 Martian Mining
POJ 2948 Martian Mining
题目大意:
NASA在火星发现了一个矿场矩阵。矩阵中的每个单元格都有两种矿Yeyenum和Bloggium。我们知道每个单元格中这两种矿的数量。NASA决定在北边建造Bloggium的矿石精炼厂,在西边建造Yeyenum的矿石精炼厂。于是需要我们把bloggium矿石向北运(行号等于0的方向),把Yeyenum矿石向西运(列号等于0的方向)。但由于矿石的不稳定在建造传送带时有特殊要求。求建造传送带后两种矿石最多能收集多少。
解题思路:
dp[i][j]代表着从(0,0)到(i,j)这两点间组成的矩阵最多能收集多少矿石。
Blo[i][j]代表Bloggium这种矿石如果从点(i,j)向北运能运多少。
yey[i][j]代表Yeyenum这种矿石如果从点(i,j)向西运能运多少。
下面是代码:
#include <stdio.h> #include <string.h> int dp[505][505]; int yey[505][505]; int blo[505][505]; int max(int a,int b) { if(a<b)a=b; return a; } int main() { int n,m; while(scanf("%d%d",&n,&m),n||m) { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",&yey[i][j]); if(j!=0)yey[i][j]+=yey[i][j-1]; } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",&blo[i][j]); if(i!=0)blo[i][j]+=blo[i-1][j]; if(i==0) { if(j==0) { dp[0][0]=max(blo[0][0],yey[0][0]); } else { dp[0][j]=max(dp[0][j-1]+blo[0][j],yey[0][j]); } } else { if(j==0) { dp[i][0]=max(dp[i-1][0]+yey[i][0],blo[i][0]); } else { dp[i][j]=max(dp[i-1][j]+yey[i][j],dp[i][j-1]+blo[i][j]); } } } } printf("%d\n",dp[n-1][m-1]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。