クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-7 Bribe the Prisoners（2009 Round 1C C）」(p.121)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-7 Bribe the Prisoners（2009 Round 1C C）」(p.121)
のコードをPythonで書き直したものとなっています。

入力


P\,Q\\A_1\,…\,A_Q

入力例1



8 1
3

入力例2



20 3
3 6 14


解答

MAX_Q = 100
INF = float('inf')

# 入力
P, Q = map(int,input().split())
A = [None] * (MAX_Q)
A[1:Q+1] = list(map(int,input().split()))    # Aには1-indexedでデータが入っている

# dp[i][j] := (i, j)を解放するのに必要な金貨
dp = [[None] * (MAX_Q + 2) for _ in range(MAX_Q + 1)]

# 簡単のため、端をAに追加する
A[0] = 0
A[Q + 1] = P + 1

# 初期化
for q in range(Q + 1):
    dp[q][q + 1] = 0

# 幅が小さい順にdpを埋めていく
for w in range(2, Q + 2):
    for i in range(Q - w + 2):
        # dp[i][j]を計算する
        j = i + w
        t = INF
        
        # 最初に解放する囚人をすべて試し、最小のコストのものを探す
        for k in range(i + 1, j):
            t = min(t, dp[i][k] + dp[k][j])
        
        # 最初の解放では解放する囚人に関わらずA[j] - A{i} - 2の金貨が必要
        dp[i][j] = t + A[j] - A[i] - 2
    
print(dp[0][Q + 1])