You are not logged in. Please login at www.codechef.com to post your questions!

×

CT3 - Editorial

PROBLEM

Practice

Contest

Author: D. Vishnu Vardhan reddy

Tester: D. Vishnu Vardhan reddy

Editorialist: D. Vishnu Vardhan reddy

DIFFICULTY:

SIMPLE

PREREQUISITES:

recursion

PROBLEM:

There are 'n' cities in a line. Each city contains some value in it. A thief is going to steal the maximal value from these cities, but he can’t steal in two adjacent cities because police of the stolen city will alert his two neighboring cities, left and right side. What is the maximum stolen value ?

EXPLANATION:

While reaching city i thief has two options, either he robs it or leave it. Let dp[i] represents the maximum value stolen so far on reaching city i. We can calculate the value of dp[i] as following –

dp[i] = max (hval[i] + dp[i-2], dp[i-1])

hval[i] + dp[i-2] is the case when thief decided to rob city i. In that situation maximum value will be the current value of city + maximum value stolen till last robbery at city not adjacent to city i which will be city i-2.

dp[i-1] is the case when thief decided not to rob city i. So he will check adjacent city for maximum value stolen till now.

Thief will consider both options and decide whether to rob or not and maximum of both values will be the maximum stolen value till reaching city i.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

asked 13 Sep, 21:20

dvvr's gravatar image

2★dvvr
112
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,010
×1,063
×296
×6

question asked: 13 Sep, 21:20

question was seen: 124 times

last updated: 13 Sep, 21:20