Hello this is my first blog post, could you please help me with this problem? You are given a stack of N elements, you want to pop all the elements performing one of the three operations: Pop 1 element, Pop 2 elements, Pop half elements. Every operations has a cost in money, based on the number of elements in the stack. You are given 3 arrays, array U, D and M. The i-th element of the array is the cost (in money) of performing the operation when the stack has i+1 elements in it. Every operation has also a cost in energy: Pop 1 restores 1 energy, Pop 2 doesn't change your energy, Pop half costs 1 energy. You start with E energy, and can never go under 0 energy. Find the minimum cost in money you need to pop all the stack, while remaining with non-negative energy. Input limits: N <= E <= 1000000, Ui and Di and Mi <= 10^9, memory limit 1MiB, time limit 1s.

The 3 arrays are given in the form of 4 integers each, V0, A, B, C. Every element i-th of each array can be generated using the formula Vi = (Vi-1 *A + B)%C

For example the integers:

13 4 7 17

1 3 9 19

7 9 9 13

with N = 5 generate the arrays U = [ 13,8,5,0,13 ] D = [ 1,12,7,11,4 ] M = [ 7,7,7,7,7 ]

I tried to use dynamic programming to solve this problem. If the only operations possible were pop1 and pop2, i could keep only 2 rows of the dp table at a time, and it would be fine, but since there is the pop half operation, i need to remember N/2 states and it goes out of memory.