Minimum cost problem, only 1MiB

Revision en1, by marcorubini301, 2018-04-16 00:45:02

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.

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.

Tags #dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English marcorubini301 2018-04-16 16:03:54 319
en3 English marcorubini301 2018-04-16 00:52:15 15 Tiny change: 'limit 1MiB.\n\nI tri' -> 'limit 1MiB, time limit 1s.\n\nI tri'
en2 English marcorubini301 2018-04-16 00:48:54 2 Tiny change: ' memory.\n\n' -> ' memory.\n' (published)
en1 English marcorubini301 2018-04-16 00:45:02 1190 Initial revision (saved to drafts)