just_for_one's blog

By just_for_one, history, 3 years ago, In English

Given 2 arrays, array A (containing only 0s and 1s) and the other cost array B of the same size. We needed to convert all the elements of array A to 1 in minimum cost. For every ith element in the array A, converting from 0 to 1 requires B[i] cost but if A[i-1] and A[i+1] are 1 then A[i] can be converted to 1 with 0 cost. Return the minimum possible cost to convert all 0s to 1s. My approach- Isn't this simply $$$dp[i]=min(dp[i-1],dp[i-2])+cost[i]$$$;

Can someone please confirm?

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by just_for_one (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

let dp[i]=ans for arr[0....i] There will be two case case1 arr[i]=1, then dp[i]=dp[i-1] case2 arr[i]=0, then dp[i]=dp[i-2]+cost[i]

»
3 years ago, # |
  Vote: I like it -18 Vote: I do not like it

don't think dp would work here, how you will track for i+1 ??

instead, build a min Heap{cost,index} and update considering the i-1, and i+1 and a[i] value.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the main constraint is this that you cant leave two consecutive zeros without being buyed. so you can make recursive calls with taking into account the state of last index that you buyed that zero or not