提出番号 | 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))
```