SPOJ - Candy (SAMER08C)

Problem Statement:
SPOJ - Candy (SAMER08C)

Summary:
Given a box of candy of dimension NxM \(\leq 10^5\), where each cell contains at most 1000 candies, find the maximum number of candies can be collected, with the following rule:
If we pick a candy on cell (i,j), then the row i-1 and row i+1 will be emptied, as well as the neighboring cells to cell (i,j).



Solution:
This is a very neat problem! First we do a DP on each row and store the maximum number of candies obtainable from that row, and then DP on these values to find the answer. Implementation:

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

int v[100003], h[100003];
int a[100003];
int N, M;

int main(){
    while( scanf("%d %d", &N, &M), N+M != 0 ) {
        for(int k=0;k<N;++k){
            for(int i=0;i<M;++i){
                scanf("%d", &a[i]);
            }
            h[M] = h[M+1] = 0;
            for(int i=M-1;i>=0;--i){
                h[i] = max(h[i+2] + a[i], h[i+1]);
            }
            v[k] = h[0];
        }
        h[N] = h[N+1] = 0;
        for(int i=N-1;i>=0;--i){
            h[i] = max(h[i+2] + v[i], h[i+1]);
        }
        printf("%d\n", h[0]);
    }
    return 0;
}