Question Name:Stack of Bricks

#include <stdio.h>
long long min(long long a, long long b) { return (a<b?a:b); }
int main() {
    int T,n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int t[n],i;
        long long best[n+3], suff[n+3];
        for ( i=n; i<n+3; i++) best[i] = suff[i] = 0;
        for (i=0; i<n; i++) scanf("%d", &t[i]);
        for ( i=n-1; i>=0; i--) suff[i] = suff[i+1] + t[i];
        for ( i=n-1; i>=0; i--)
            best[i] = suff[i] - min(best[i+1], min(best[i+2], best[i+3]));
        printf("%lld\n", best[0]);
    }
    return 0;
}
  • Problem Description
    You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. 

    You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.

    Input Format

    First line will contain an integer T i.e. number of test cases. There will be two lines corresponding to each test case: first line will contain a number N i.e. number of elements in the stack and next line will contain N numbers i.e. numbers etched on bricks from top to bottom.

    Constraints

    1 <= T <= 5 
    1 <= N <= 10^5 
    0 <= each number on brick <= 10^9

    Output Format

    For each test case, print a single line containing your maximum score.


  • Test Case 1
    Input (stdin)2
    5
    999 1 1 1 0
    5
    0 1 1 1 999
    Expected Output1001
    999
  • Test Case 2
    Input (stdin)2
    5
    999 0 1 1 1
    5
    1 1 1 0 999
    Expected Output1000
    1000

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.