2969. Minimum Number of Coins for Fruits II

Use DP + Fenwick tree.

There is another creative solution using multiset instead of Fenwick.

Imagine we want to calculate dp[i] which is the answer to the problem for the first i fruits.

If we buy lth fruit from the set of indices: [(i + 1) / 2, (i + 1) / 2 + 1, (i + 1) / 2 + 2, ..., i - 1], then we can get fruits l + 1, l + 2, ..., i for free.

We just need to get all the first l - 1 fruits as well and the minimum price for that, is dp[l - 1].

So at the index i, we are looking for such an index l that dp[l - 1] + prices[l] is as minimum as possible.

We can store these values in a multiset and update the values in it.