I was solving [CSES — Towers](https://cses.fi/problemset/task/1073) 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?
↵
↵
```↵
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?
