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