Lyrebird1101's blog

By Lyrebird1101, history, 4 years ago, In English

Hi I am stuck with this problem for a while now,can someone help me with this :

Given two arrays A and B, you have to make the Array A "Special", i.e. an array in which no two adjacent elements are the same, you can do it by incrementing an element by 1. However each increment of element A[i] comes with a cost, which is represented by B[i], determine the minimum cost incurred in making element A special.

For example:

A = [4,3,3,1,5] B = [1,2,5,5,6] There are two possible ways of making A Special, (i) by incrementing A[2] at a cost of B[2], thus A becomes [4,3,4,1,5] at a total cost of 5. (ii) by incrementing A[1] at a cost of B[1], but now A[1] = A[0] hence we again have to perform the increment operation, on either A[0] or A[1], the minimum cost as you must've guessed would be by incrementing A[0], thus A finally becomes [5,4,3,1,5] at a total cost of B[1]+B[0] = 3, which is less than the cost incurred in the first option, and hence is the answer to this problem.

Similarly for

A = [4,3,3,3,1,5] B = [1,2,5,5,6,5]

The minimum cost would be 5, i.e. by incrementing A[2], the other option is to increment A[0], A[1], and A[3] at a total cost of 8.

How do I proceed with this problem, please help.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it