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 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 feodorv C 0.01s
02 Morass Cpp14 0.04s
03 tariqiitju Cpp14 0.04s
04 sakib_muhit Cpp14 0.04s
05 jalal Cpp14 0.04s
06 rajdipsaha Cpp 0.04s
07 a_rahman Cpp14 0.05s
08 njrafi Cpp14 0.06s
09 ahqmrf Cpp14 0.43s
10 clcrr Cpp14 0.43s
11 alhelal_cse Cpp14 0.52s

Your feedback is our precious!

Or call +88 02 9853138 for support