Maximum-Cup 2018 D Many Go Round(2)

前回の続き

解答通りに、dp[i][j] := i番目までの燃料タンクを使って番号jの休憩所に止まるための周回の最小回数で再帰関数を作ってみる。

INF = 10**9+7

def rec(pos, j):
    if pos == -1:
        if j == L:
            return 0
        return INF
    # pos 番目を使わない
    ans = rec(pos-1, j)
    ans = min(ans, rec(pos-1, (j+a[pos])%M)+(j+a[pos])//M)
    return ans

ans = rec(N-1, 0)
print(ans)
print('Yes') if ans < X else print('No')

こっからよくわかんないんだけど、DPに移せない。なんでなんだろうなぁ。明日またやります。