Suppose you have been given two arrays of length N ( 1 < N <= 100000), say A[1 .. N] & B[1 .. N], Now you have to output another array, C[1 .. N] such that:
C[ i ] = A[ i ] + min(C[ j ] — B[ j ] * B[ i ]) for all 0 <= j < i.
Note: C[0] = A[0]
for example: Suppose A = [3, 9, 4] and B = [2, 4, 2]
C[0] = A[0] = 3
C[1] = 9 + C[0] — B[1] * B[0] = 4
C[2] = 4 + min(C[0] — B[0] * B[2], C[1] — B[1] * B[2]) = 4 + min(-1, -4) = 0
Ranges :
0 < N < 100000
-10^9 <= A[i] <= 10^9
0 < B[i] < 10^7
Besides the brute force solution, I have thought of segment tree, But it will fail to make range minimum query.
I think some new data-structure will be used, which i have not known. Could somebody suggest the data structure for the same or how to problem the with it...
Thanks in Advance