結果

提出番号	1807
提出者	nadare881
言語	Python3
提出日時	2018-08-04 13:59:31
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

# -*- coding: utf-8 -*-
from itertools import product
def inpl(): return list(map(int, input().split()))
N = int(input())
T = inpl()
A = [inpl() for _ in range(N)]

DP = [16*1000 + 1 for _ in range(2**N)]
tmp = []
P = [2**i for i in range(N)]
for i in range(N):
    DP[2**i] = T[i]

tmp = set(P)
for _ in range(N-1):
    tmp2 = set()
    for t in tmp:
        for j, p in enumerate(P):
            s = 0
            if t&p:
                continue
            for i in range(N):
                if (t >> i) % 2:
                    s += A[i][j]
            DP[t|p] = min(DP[t|p], DP[t] + max(0, T[j] - s))
            tmp2.add(t|p)
    tmp = tmp2
print(DP[-1])