I was solving CSES — Towers and came with an alternate problem which I think can be solved using DP somehow:
You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.
You must process the cubes in the given order. You can always either place the cube on top of an existing tower, begin a new tower or discard the current cube. You may discard at most K cubes. What is the minimum possible number of towers?
Constraints:
(Don't worry about the constraints, if you can think of any polynomial-time solution, please let me know)
1 <= N <= 1e5,
1 <= cube sizes <= 1e9
0 <= K <= N
eg. N = 4; cubes = [3, 8, 2, 1]; K = 1
Output: 1
==> Discard cube with size 3 or 8 and use the rest to build 1 tower
Any ideas to solve this efficiently?
It is possible to think of a greedy way.
If we have only one tower and the height of the top cube is equal to h, then the optimal way is to put the nearest cube (from the right) whose height is smaller than h. If we don't find any suitable cube, then we start another tower by the first cube that has not been taken yet.
You can use a multiset to do it, the multiset will store the height of the top cube of each tower. Iterate over all cubes, the current cube will be putten above the smallest cube in the multiset which is greater than the current cube, now the current cube is the top of this tower, so you should erase the older top, if you can't find this greater cube, you should insert the current cube as a new tower.
You didn't read the problem statement :)
Oh, sorry.
Ok. I will try.