Non-Decreasing Array Problem

Revision en3, by ed1d1a8d, 2017-02-04 22:37:34

Here is a problem my friend smurty posed:

Say we are given an array of non-negative integers of length n, representing stacks of dirt of certain heights. We can move one piece of dirt from one pile to an adjacent pile for cost 1. What is the minimum cost it takes to transform this array to be non-decreasing?

Neither me nor my friend could come up with a polynomial time solution in n to this problem. Can CF think of something?

EDIT: BUMP

Tags non-decreasing, array, integer

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English ed1d1a8d 2017-02-04 22:39:00 14 Tiny change: 'something?' -> 'something?\n\nEDIT: BUMP'
en4 English ed1d1a8d 2017-02-04 22:38:27 14 BUMP
en3 English ed1d1a8d 2017-02-04 22:37:34 12 Tiny change: 'mething?\n' -> 'mething?\n\nEDIT: BUMP'
en2 English ed1d1a8d 2017-02-02 05:27:21 6 Tiny change: 'mething?\n\n\n\n' -> 'mething?\n'
en1 English ed1d1a8d 2017-02-02 05:26:54 495 Initial revision (published)