UVALive - 3530 Martian Mining

제목: n*m 격자 중 각 칸에 A, B 두 종류의 광물이 있음을 제시한다. A광은 반드시 오른쪽에서 왼쪽으로 운송해야 하고 B광은 아래에서 위로 운송해야 한다. 파이프는 구부러지거나 부러지지 않는다. 수집한 A, B광의 총량은 최대한 크다.
사고방식: 각 칸마다 A가 아니면 B광의 파이프이기 때문에 두 가지 선택밖에 없다.
그래서 dp[i][j]=max(dp[i][j-1]+b[i][j], dp[i-1][j]+a[i][j]), 그 중에서 a[i][j], b[i][j]는 각각 오른쪽에서 왼쪽으로, 아래에서 위로 운송하는 방식의 전 j, 전 i의 총 광수를 대표한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 505;

int a[MAXN][MAXN],b[MAXN][MAXN],dp[MAXN][MAXN];
int n,m;

int main(){
    while (scanf("%d%d",&n,&m) != EOF && n+m){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++){
                scanf("%d",&a[i][j]);
                a[i][j] += a[i][j-1];
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++){
                scanf("%d",&b[i][j]);
                b[i][j] += b[i-1][j];
            }
        memset(dp,0,sizeof(dp));
        int ans = 0;
        for (int i = 1; i <= n; i++)
            for (int 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
",dp[n][m]);
    }
    return 0;
}