SPOJ - MARTIAN

Problem Statement:
SPOJ - MARTIAN

Summary:
A field of dimension RxC has some amount of minerals on each cell, such that each cell (i,j) has A[i][j] mineral of first type and B[i][j] mineral of second type. Mineral of first type is collectible only on the left side of the field, while mineral of second type is collectible only on the top side of the field. For each cell on the field, we can only build either a straight conveyor belt to the left, or a straight conveyor belt to the top. No conveyor belt can cross each other. Minerals are transported via such belts. Find the maximum possible amount of minerals collectible.



Solution:
I think this is an interesting DP problem, and there is a nice recursive relationship to solve this:
1. Let M(i,j) be the maximum amount of minerals collectible from field [0..i][0..j].
2. Consider cell(i,j). We can either send the mineral of type A to the left, hence building a belt across the i-th row, or we can send the mineral of type B to the top and built a conveyor belt across j-th column. If we send to the left, we find the total minerals collectible along this belt, plus M(i-1,j). Or, if we send to the top, we do the same thing and consider M(i,j-1). Then M(i,j) is the maximum of the two choices.

Before proceeding with implementation, we need to make sure that each check on each cell will only take O(1) time and O(RC) in total. Hence to do that we need to precompute the 1D array sum of each rows of A and each columns of B.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int sum[2][503][503];
int dp[503][503];
int R, C;

void solve(){
    for(int i=0;i<R;++i){
        for(int j=0;j<C;++j){
            int tmp1 = sum[0][i][j];
            int tmp2 = sum[1][i][j];
            if(j>0) tmp1 += dp[i][j-1];
            if(i>0) tmp2 += dp[i-1][j];
            dp[i][j] = max(tmp1, tmp2);
        }
    }
    printf("%d\n", dp[R-1][C-1]);
}

int main(){
    while(scanf("%d %d", &R, &C), R+C!=0){
        int s;
        for(int i=0;i<R;++i){
            for(int j=0;j<C;++j){
                scanf("%d", &s);
                sum[1][i][j] = s;
                if(j>0) sum[1][i][j] += sum[1][i][j-1];
            }
        }
        for(int i=0;i<R;++i){
            for(int j=0;j<C;++j){
                scanf("%d", &s);
                sum[0][i][j] = s;
                if(i>0) sum[0][i][j] += sum[0][i-1][j];
            }
        }
        solve();
    }
    return 0;
}