Блог пользователя dush1729

How to solve Chef and Way using Dynamic Programming?
Автор dush1729, история, 8 лет назад, По-английски

I am trying to solve this using dynamic programming with complexity of O ( N ^ 2 ) which will give TLE because N <= 10 ^ 5.

Problem Link

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First, store an array b, b[i] = log2(a[i]) to get rid of big numbers.
Now, calculate the following DP:

DP[1]=0

DP[i]=min(DP[j]+b[i]) for all i - k <  = j < i (note that the problem is now changed to addition instead of multiplication becasue log(a * b) = log(a) + log(b)
Store the best path, and calculate the product of all A[i]'s that occur in the path.

You can solve the above DP in O(nlogn) by maintaining a set of the last k DP values.

Code

→ Ответить