## Wednesday, October 22, 2014

### 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;
}