結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 24ms 33120KB
2 AC 100% 22ms 32912KB
3 AC 100% 24ms 32624KB
4 AC 100% 22ms 32896KB
5 AC 100% 23ms 32720KB
6 AC 100% 24ms 32736KB
7 AC 100% 20ms 33200KB
8 AC 100% 21ms 32944KB
9 AC 100% 20ms 32944KB
10 AC 100% 20ms 33280KB
11 AC 100% 39ms 32688KB
12 AC 100% 28ms 33296KB
13 AC 100% 42ms 32464KB
14 AC 100% 28ms 33040KB
15 AC 100% 27ms 32592KB
16 AC 100% 21ms 32704KB
17 AC 100% 20ms 33200KB
18 AC 100% 20ms 33152KB
19 AC 100% 63ms 32960KB
20 AC 100% 61ms 33264KB
21 AC 100% 22ms 33056KB
22 AC 100% 116ms 32992KB
23 AC 100% 24ms 32560KB
24 AC 100% 235ms 34128KB
25 AC 100% 75ms 33056KB
26 AC 100% 112ms 33136KB
27 AC 100% 230ms 34160KB
28 AC 100% 67ms 32880KB
29 AC 100% 1109ms 38000KB
30 AC 100% 120ms 32848KB

ソースコード

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))