HackerRank: Play Game

HackerRank: Play Game

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.

Suppose numbers written on bricks are a[0], a[1]....., a[n-1] where a[0] is the bottom-most brick.
Consider another array of prefix sum i.e. sum[n]
where sum[i] = a[0] + a[1] + ....+ a[i]

Consider another array dp[n]
where dp[i] = maximum score of first player for stack a[0],a[1]...,a[i] when he is playing optimally. 

It is obvious that,
dp[0] = a[0]
dp[1] = a[0] + a[1]
dp[2] = a[0] + a[1] + a[2]

Now suppose that dp[0], dp[1],....., dp[k-1] has been calculated and we want to calcualte dp[k].

For kth brick, first player will have 3 options.

1. Pick one
   Then first player will get a[k] and his opponenet will get dp[k-1] so first will get { (sum[k-1] - dp[k-1]) + a[k] } in total.
2. Pick two
   Then first player will get a[k]+a[k-1] and his opponenet will get dp[k-2] so first will get { (sum[k-2] - dp[k-2]) + a[k]+ a[k-1] } in total.
3. Pick three
   Then first player will get a[k]+a[k-1]+a[k-2] and his opponenet will get dp[k-3] so first will get { (sum[k-3] - dp[k-3]) + a[k]+ a[k-1] +a[k-2] } in total.

so dp[k] = max {(sum[k-1] - dp[k-1]) + a[k] ,(sum[k-2] - dp[k-2]) + a[k]+ a[k-1], (sum[k-3] - dp[k-3]) + a[k]+ a[k-1] +a[k-2] }

This can be calculated in O(1) time, so total time needed will be O(n).

int main() 
{ 
    int t; 
    cin >> t;
    while(t--) 
    {
        pre[0]=0;
        LL n,i,j; 
        cin >> n; 
        assn(n,1,100000);
        for(i=n; i>0; i--)
        {
            cin >> val[i];
            assn(val[i],0ll,1000000000ll);
        } 
        for(i=1; i<=n; i++) 
            pre[i]=pre[i-1]+val[i];
        dp[0]=0;
        dp[1]=val[1];
        dp[2]=dp[1]+val[2];
        dp[3]=dp[2]+val[3]; 
        for(i=4; i<=n; i++)
        {
            dp[i]=max(-1ll,pre[i-1]-dp[i-1]+val[i]);
            dp[i]=max(dp[i],pre[i-2]-dp[i-2]+val[i]+val[i-1]); 
            dp[i]=max(dp[i],pre[i-3]-dp[i-3]+val[i]+val[i-1]+val[i-2]); 
        }
        cout << dp[n] << endl; 
    }
    return 0; 
}

http://www.cnblogs.com/boring09/p/4483376.html
We may save space: no need best(or dp) array, just 3 variables, we even don't need prefix sum array.

23         for (int i = 1; i <= N; i++)
24             cin >> score[i];
25         for (int i = N; i >= 1; i--)
26             sum[i] = score[i] + sum[i + 1];
27         best[N] = sum[N];
28         best[N - 1] = sum[N - 1];
29         best[N - 2] = sum[N - 2];
30         for (int i = N - 3; i >= 1; i--)
31             for (int j = 1; j <= 3; j++)
32                 best[i] = max(best[i], sum[i] - best[i + j]);
33         cout << best[1] << endl;

https://codepair.hackerrank.com/paper/QhqF1LdT?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
        for (int i=n-1; i>=0; i--) suff[i] = suff[i+1] + t[i];
        for (int i=n-1; i>=0; i--)
            best[i] = suff[i] - min(best[i+1], min(best[i+2], best[i+3]));
https://codepair.hackerrank.com/paper/BX8o6bAv?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
def solve(xs):
    xn = len(xs)
    ss = [(0, 0)]
    for ix in range(xn):
        eix = xn - ix - 1
        best = None
        for dx in (1, 2, 3):
            if eix + dx > xn:
                continue
            p = sum(xs[eix:eix + dx])
            a, b = ss[ix + 1 - dx]
            r = (b + p, a)
            if best is None or best[0] < r[0]:
                best = r
        ss.append(best)
    return ss[-1][0]