GoogleCodeJam 2009 Round 1C C. Bribe the Prisoners

動的計画法。
i番目の囚人の位置をp[i]として、i番目の囚人とj番目の囚人を解放した後、i番目とj番目の間に居る囚人を解放するのに要するコインをcoin[i][j]とすると。

coin[i][j] = min_i<c<j coin[i][c]+coin[c][j] + p[j]-p[i]-2

for n in range(input()):
    P,Q = [int(x) for x in raw_input().split()]
    rel = [0]+[int(x) for x in raw_input().split()]+[P+1]
    
    coin = [[0]*(Q+2) for i in range(Q+2)]
    
    for w in range(2,Q+2):
        for i in range(Q+2-w):
            coin[i][i+w] = min([coin[i][c]+coin[c][i+w] for c in range(i+1,i+w)])+(rel[i+w]-rel[i]-2)
    
    print "Case #%s: %s" % (n+1,coin[0][Q+1])