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?