結果

提出番号	2335
提出者	testes89
言語	Python3
提出日時	2020-03-24 22:58:39
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

import sys
input = sys.stdin.readline

N = int(input())
t = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(N)]

inf = 10**18

# dp[bitset] := bitが1のアルゴリズムは学習済みで、
#               残りのアルゴリズムを最適に学習したときの最小コスト
dp = [inf]*(1 << N)
dp[-1] = 0


def solve(bitset):
    if dp[bitset] < inf:
        return dp[bitset]

    for i in range(N):
        if bitset & (1 << i):
            continue

        # 学習済みアルゴリズムによって減少する時間
        reduce = sum(a[i][j] for j in range(N) if bitset & (1 << j))

        dp[bitset] = min(
            dp[bitset],
            solve(bitset | (1 << i)) + t[i] - reduce
        )

    return dp[bitset]


print(solve(0))