DCP-37: Walky Walk Back to All Problems

Medium Divide and Conquer > Dynamic Programming

Bob is developing a new game. In the game, there will be N blocks, numbered from 1 to N. Initially a player will be standing at block numbered 1 and can jump to other blocks. The player’s first jump should be from block 1 to block 2. Then the next jumps can be: 1. If the jump is in forward direction, the length must be one block longer than the previous jump. 2. If the jump is in backward direction, the length must be same as the previous jump. For example, after the first jump (when the player is at block 2), s/he can jump back to block 1 or block 4. Now each block contains a surcharge, if you jump on a certain block you have to pay that block’s surcharge (it doesn’t matter whether s/he visited the block before). Now the player’s target will be to go from block 1 to block N by paying minimum surcharge possible. Can you find that minimum surcharge? As the player is initially at block 1 and didn’t jump into the block 1 so s/he will not pay the surcharge for block 1. But if in any subsequent jump one player jumps to block 1, s/he must pay. Input: ------ Input starts with an integer **T (≤ 10)**, denoting the number of test cases. The first line of each case contains the integer **N, 2 ≤ N ≤ 1000**, the number of blocks. Then the next line contains N integers separated by space, where I’th integer **( 1 <= I <= N)** denotes the surcharge of I’th block. These integers will be between **1 and 500** Output: ------- For each case, print the case number and the minimum surcharge a players needs to give to go from block 1 to block N. See the samples for exact formatting. Sample Input ------------ 2 6 1 2 3 4 5 6 8 2 3 4 3 1 6 1 4 Sample Output ------------- Case 1: 12 Case 2: 14

Problem Setter:

Ahmad Faiyaz

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C/C++ 1.00
Java 2.00
C# 2.00
PHP 2.00

Problem Stats




# User Language Timing
01 tariqiitju Cpp 0.04s
02 sakib_muhit Cpp 0.04s
03 jalal Cpp 0.04s
04 a_rahman Cpp 0.05s
05 njrafi Cpp 0.06s
06 ahqmrf Cpp 0.43s
07 clcrr Cpp 0.43s
08 alhelal_cse Cpp 0.52s

Your feedback is our precious!

Or call +88 02 9853138 for support