結果

提出番号	2290
提出者	ne0n
言語	Python3
提出日時	2019-12-07 22:45:06
問題名	(70)アルゴリズムのお勉強
結果	TLE
点数	0%

---

テストケース

ソースコード

n = int(input())
t = list(map(int,input().split()))
a = list()
dp = [10000 for i in range(2**n)]
for i in range(n):
    a.append(list(map(int,input().split())))
oo = "0"*n
#for i in range(n):
#    omae = oo[:i] + "1" + oo[i+1:]
#    omae_int = 0
#    for j in range(n):
#        omae_int += 2**j*int(omae[-1*(j+1)])
#    dp[omae_int] = 0
dp[0] = 0
def func(name):
    for i in range(n):
        if name == "1"*n:
            break
        if name[i] == "1":
            continue
        add = 0
        for j in range(n):
            if name[j] == "1":
                add += a[-1*(j+1)][-1*(i+1)]
        after = name
        after = after[:i] +"1"+after[i+1:]
        after_int = 0
        name_int = 0
        for j in range(n):
            after_int += (2**j)*int(after[-1*(j+1)])
            name_int += (2**j)*int(name[-1*(j+1)])
        
        if t[i]-add > 0:
            dp[after_int] = min(dp[after_int],dp[name_int] + t[i] - add)
        else:
            dp[after_int] = min(dp[after_int],dp[name_int])
        func(after)
omae = "0"*n
func(omae)
print(dp[2**n-1])