Domino Effect Problem
Python

N, H = map(int, raw_input().split())
D = map(int, raw_input().split())

# map from (number of dominoes, distance to last domino) to                                                                                                        
# the number of moves needed to adjust the first number of dominoes                                                                                                
# exactly that far.                                                                                                                                                
M = {}
M[1,0] = 0

for i in xrange(2, N+1):      # i = number of dominos to try                                                                                                       
  for d in xrange(H*(i-1)+1):
    M[i,d] = 1e9
  for d in xrange(H*(i-1)+1): # position of last domino                                                                                                            
    for e in xrange(1, H+1):  # distance from last domino to previous one                                                                                          
      if d-e &gt; H*(i-2): continue
      if d-e &lt; 0: continue
      if sum(D[:i-1]) == d:
        # don't move last domino, arrange rest                                                                                                                     
        M[i,d] = min(M[i,d], M[i-1,d-e])
      else:
        # arrange rest, move last domino to right location                                                                                                         
        M[i,d] = min(M[i,d], 1 + M[i-1,d-e])

print M.get((N,sum(D)), -1)


Standard dynamic programming.  Runs pretty much instantaneously on the example inputs.  How big a problem do we have to solve in under a second?