Complexity of above solution is O(n)
On Jan 5, 10:50 pm, suhash <suhash.venkat...@gmail.com> wrote:
> 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.
