poj 2948 Martian Mining_容易dp

poj 2948 Martian Mining_简单dp

题目链接

题意：给一个两个n*m的图，向左统计或者向上统计，求最大的价值

思路：图1先向左统计，图2先向上统计，最后dp统计最优,dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j-1]+b[i][j]);

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 502
int mat_a[MAXN][MAXN],mat_b[MAXN][MAXN];
int a[MAXN][MAXN],b[MAXN][MAXN],dp[MAXN][MAXN];
 
int main(int argc, char** argv) {
	int n,m,i,j;
	while(scanf("%d%d",&n,&m)!=EOF,n+m){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				scanf("%d",&mat_a[i][j]);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				scanf("%d",&mat_b[i][j]);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				a[i][j]=a[i][j-1]+mat_a[i][j];
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				b[i][j]=b[i-1][j]+mat_b[i][j];
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j-1]+b[i][j]);
	
		printf("%d\n",dp[n][m]);
	}
	return 0;
}