So, I came up with this problem:
You are given an array $$$a$$$ of length $$$N$$$. Additionally, you are given a set of $$$q$$$ operations, where each operation is defined by a pair $$$(s, p)$$$. You may perform any number of operations from this set in any order.
When you apply an operation $$$(s, p)$$$ to the current state of the array $$$a$$$, the following process occurs:
- You accumulate the sum of elements at indices $$$s, s+p, s+2p, \dots, s+kp$$$, where $$$s+kp$$$ is the largest valid index such that $$$s+kp \le |a|$$$.
- All elements at the visited indices are removed from the array.
- The remaining elements are re-indexed consecutively, preserving their original relative order.
Your goal is to perform a sequence of operations such that the total accumulated sum of all chosen elements does not exceed $$$maxW$$$, and this sum is as large as possible
Right now, there is no better solution than exponential, but I'm wondering is there some polynomial solution?
