提出番号 | 2245 |
---|---|

提出者 | taotao54321 |

言語 | C++ |

提出日時 | 2019-08-19 04:03:22 |

問題名 | (70)アルゴリズムのお勉強 |

結果 | AC |

点数 | 100% |

テストケース | 結果 | 得点 | 実行時間 | メモリ使用量 |
---|---|---|---|---|

1 | AC | 100% | 2ms | 7904KB |

2 | AC | 100% | 2ms | 8224KB |

3 | AC | 100% | 2ms | 7552KB |

4 | AC | 100% | 2ms | 7840KB |

5 | AC | 100% | 2ms | 7824KB |

6 | AC | 100% | 2ms | 8672KB |

7 | AC | 100% | 2ms | 8432KB |

8 | AC | 100% | 2ms | 7840KB |

9 | AC | 100% | 2ms | 7568KB |

10 | AC | 100% | 2ms | 8688KB |

11 | AC | 100% | 2ms | 8176KB |

12 | AC | 100% | 2ms | 8656KB |

13 | AC | 100% | 2ms | 7824KB |

14 | AC | 100% | 2ms | 7840KB |

15 | AC | 100% | 2ms | 7840KB |

16 | AC | 100% | 2ms | 7936KB |

17 | AC | 100% | 2ms | 7664KB |

18 | AC | 100% | 2ms | 8688KB |

19 | AC | 100% | 2ms | 8640KB |

20 | AC | 100% | 2ms | 8096KB |

21 | AC | 100% | 2ms | 7856KB |

22 | AC | 100% | 3ms | 8320KB |

23 | AC | 100% | 2ms | 8448KB |

24 | AC | 100% | 4ms | 8656KB |

25 | AC | 100% | 2ms | 8672KB |

26 | AC | 100% | 3ms | 8192KB |

27 | AC | 100% | 4ms | 8560KB |

28 | AC | 100% | 2ms | 7664KB |

29 | AC | 100% | 12ms | 7856KB |

30 | AC | 100% | 3ms | 7936KB |

```
/**
*
*/
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1010000000000000017LL;
#define FOR(i, start, end) for(long long i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)
//--------------------------------------------------------------------
void solve() {
long long N; cin >> N;
vector<long long> T(N);
REP(i, N) { cin >> T[i]; }
vector<vector<long long>> M(N, vector<long long>(N));
REP(i, N) REP(j, N) {
cin >> M[i][j];
}
vector<long long> dp(1LL<<N, INF);
dp[0] = 0;
REP(i, 1LL<<N) {
REP(j, N) {
if(i&(1LL<<j)) continue;
long long t = T[j];
REP(k, N) {
if(i&(1LL<<k))
t -= M[k][j];
}
dp[i|(1LL<<j)] = min(dp[i|(1LL<<j)], t+dp[i]);
}
}
long long ans = dp[(1LL<<N)-1];
cout << ans << "\n";
}
signed main() {
solve();
return 0;
}
```