CODEWITHSUNDEEP
dynamic-programming
sri
sri

Reputation: 11

Minimum cost to make all array elements zero

Minimum cost to make all array elements zero So the operations are as following :

A subarray of array A is a segment od contiguous elements in array A. Given an array A of N elements, you can apply the following operations as many times as you like :

Operation 1: Choose any subarray [L,R] and decrement every element in this subarray for a cost C1 Operation 2: Choose an index I such that A[i] is positive and setting A[i] = 0. The cost of this operation is C2

Our task is to find the minimum cost for making all the elements zero.

1 <= C1 <= 10 
1 <= C2 <= 10^4
1 <= A[i] <= 10^8

Upvotes: 0

Views: 1385

Answers (1)

Y.T.
Y.T.

Reputation: 2739

I will describe a divide-and-conquer algorithm here.

Idea

Notice that when we have an array, it is always optimal to do all Operation 1 before any Operation 2. Why? When you do Operation 2, for example on the array [1, 1, 3, 4], say you set the 3rd element as 0, it will make the array [1, 1, 0, 4]. Previously in the array [1, 1, 3, 4] we can do Operation 1 on interval [0, 3], but now we need two operations to do the same thing (i.e. [0, 1] and [3, 3]). As a result, it is always optimal to do all Operation 1 before any Operation 2.

Also, we notice that when we do Operation 1, we always do so such that some element will reach 0, otherwise it would be meaningless to do Operation 1. This yields a divide-and-conquer algorithm which I will illustrate with an example:

Implementation

Assume the array is [8, 4, 3, 6, 7, 9, 12, 5]. We call a recursive function solve(0, 7) which will return the cost to make all elements 0.

In solve(0, 7), we have two choices:

  1. Apply Operation 1 for three times on [0, 7], it would reduce the array to [5, 1, 0, 3, 4, 6, 9, 2], taking a cost of 3 * C1. Then recursively solve for solve(0, 1) and solve(3, 7). The answer would be 3 * C1 + solve(0, 1) + solve(3, 7).
  2. Apply Operation 2 on all elements. This will give a cost of (7 - 0 + 1) * C2 = 8 * C2.

We take whichever way resulting in a smaller cost.

Upvotes: 1

Related Questions