In any column, we can place atmost 2 pebbles.
(a) Considering an isolated column, we can place 1 or 2 pebbles.
Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4}
(b) Have an array dp[n][5][5]. Let dp[i][j][k] store the maximum sum
that can be achieved starting from column 'i' to column 'n-1' (columns
are numbered 0 - (n-1)), where row 'j' and row 'k' of column 'i-1' are
chosen. If j=0 or k=0 (then no cell is chosen). (Rows are numbered 1 -
4).
Here is the C++ code:
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define MAXN 1000+5
int n;
int a[MAXN][5];
int dp[MAXN][5][5];
int go(int i,int j,int k){
//Without loss of generality, assume always j<=k (we can
incorporate that in our code)
if(i==n) return 0;
int &ans=dp[i][j][k];
if(ans!=-1) return ans;
ans=go(i+1,0,0);
for(int h=1;h<=4;h++) if(h!=j&&h!=k) ans=max(ans,a[i][h]+go(i
+1,0,h));
if(j!=1&&k!=3) ans=max(ans,a[i][1]+a[i][3]+go(i+1,1,3));
if(j!=1&&k!=4) ans=max(ans,a[i][1]+a[i][4]+go(i+1,1,4));
if(j!=2&&k!=4) ans=max(ans,a[i][2]+a[i][4]+go(i+1,2,4));
return ans;
}
int main(){
scanf("%d",&n);
//Set 'dp' array to -1 initially
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++) for(int j=1;j<=4;j++) scanf("%d",&a[i][j]);
int ans=go(0,0,0);//maximum value
printf("%d\n",ans);
return 0;
}
On Jan 5, 10:00 pm, Decipher <ankurseth...@gmail.com> wrote:
> We are given a checkerboard which has 4 rows and n columns, and has an
> integer written in each square. We are also given a set of 2n pebbles,
> and we want to place some or all of these on the checkerboard (each
> pebble can be placed on exactly one square) so as to maximize the sum
> of the integers in the squares that are covered by pebbles. There is
> one constraint: for a placement of pebbles to be legal, no two of them
> can be on horizontally or vertically adjacent squares (diagonal
> adjacency is fine).
>
> (a) Determine the number of legal patterns that can occur in any
> column (in isolation, ignoring the pebbles in adjacent columns) and
> describe these patterns.
>
> Call two patterns compatible if they can be placed on adjacent columns
> to forma legal placement. Let us consider subproblems consisting of
> the first k columns 1 <= k <= n. Each subproblem can be assigned a
> type, which is the pattern occurring in the last column.
>
> (b) Using the notions of compatibility and type, give an O(n)-time
> dynamic programming algorithm for computing an optimal placement
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
