TopCoder problem "RowGame" used in SRM 450 (Division I Level Three)



Problem Statement

    The RowGame is a one-player game in which a single piece is moved across a board. The board consists of N squares arranged in a row, numbered 1 through N, from left to right. Each square has an associated value.



Initially, the piece is on square 1, and the current direction is right. On each turn, the player moves zero or more squares in the current direction. The direction is then reversed for the next turn. Scoring works as follows. Initially the player's score is 0. Each time the player moves from square A to square B, the sum of the values of each square between A and B, inclusive, is added to his score. Values can be negative, and the player is never allowed to make a move that will cause his score to drop below zero.



You are given a int[] board, where the i-th element (0-indexed) is the value of square (i+1). Return the maximum score that can be attained if the player is allowed to make at most k moves.
 

Definition

    
Class:RowGame
Method:score
Parameters:int[], int
Returns:long
Method signature:long score(int[] board, int k)
(be sure your method is public)
    
 

Constraints

-board will contain between 1 and 50 elements, inclusive.
-Each element of board will be between -400000000 and 400000000, inclusive.
-k will be between 1 and 400000000, inclusive.
 

Examples

0)
    
{2,-2,4,3,-10} 
3
Returns: 21
Move 1: Move to square 4. You receive 2-2+4+3 = 7 points.

Move 2: Move to square 3. You receive 3+4 = 7 points.

Move 3: Move to square 4. You receive 4+3 = 7 points.

1)
    
{-6,5}
10
Returns: 0
There is no way to get a non-negative score after the first move, so you should make no moves at all.
2)
    
{5,-6}
10
Returns: 50
In each move you can stay in square 1 and earn 5 more points.
3)
    
{10,-100,80}
3
Returns: 30
1. On the first move, you cannot move to either of the other squares because it would cause your score to drop below zero, so you must stay on square 1 and get 10 points.

2. On the second move, your direction changes to left, but since there are no squares to the left of square 1, your only option is to stay on the same square and get 10 more points.

3. Finally, on the last move, your direction changes back to right, and this time, you have two options: stay on square 1 or move to square 3. Moving to square 3 would make you lose 10 points, for a total score of 10, while staying on square 1 would get you 10 points, for a total score of 30. You choose to stay on square 1.

4)
    
{10,-100,80}
4
Returns: 90
5)
    
{-100,1,2,3,4,5,6,7,8,9,10,11,12,13,14}
400000000
Returns: 41999999900

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10664

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13904&pm=10664

Writer:

Rydberg

Testers:

PabloGilberto , Andrew_Lazarev , ivan_metelsky , Smylic

Problem categories:

Dynamic Programming, Greedy, Search