結果

提出番号	2450
提出者	keyball44
言語	Python3
提出日時	2025-01-03 10:36:00
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

inf = 10**12
import sys
N = int(input())
t = list(map(int, input().split()))
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
DP = [inf for _ in range(1<<N)]
#DP[bitset] := bitsetの状態まで最適に勉強したときにかかる時間
DP[0] = 0
for bitset in range(1<<N):
    for nx in range(N):
        if (bitset >> nx)&1:#既にnxを学んでいるので飛ばす
            continue
        learncost = t[nx]
        for i in range(N):
            if (bitset >> i)&1:
                learncost -= a[i][nx]
        learncost = max(0,learncost)
        DP[bitset | (1 << nx)] = min(DP[bitset | (1 << nx)], DP[bitset] + learncost)
print(DP[-1])