提出番号 | 2364 |
---|---|

提出者 | kya |

言語 | C++ |

提出日時 | 2020-04-27 20:39:19 |

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

結果 | AC |

点数 | 100% |

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

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

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

3 | AC | 100% | 3ms | 8480KB |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20 | AC | 100% | 3ms | 8544KB |

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

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

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

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

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

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

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

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

29 | AC | 100% | 11ms | 7728KB |

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

```
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = (1 << 30);
constexpr int MAX = (1 << 16) + 10;
void chmin (int &a, int b) {
if (a > b) a = b;
}
int main() {
int n;
cin >> n;
vector<int> t(n);
vector<vector<int>> a(n, vector<int>(n));
for (int &e : t) cin >> e;
for (auto &v : a) for (int &e : v) cin >> e;
vector<int> dp((1 << n), INF);
dp[0] = 0;
for (int s = 0; s < (1 << n); s++) {
vector<int> id;
for (int i = 0; i < n; i++) {
if (s & (1<<i)) id.push_back(i);
}
for (const int &i : id) {
int cost = t[i];
for (const int &j : id) cost -= a[j][i];
chmin(dp[s], dp[s - (1 << i)] + cost);
}
}
cout << dp[(1 << n) - 1] << '\n';
return 0;
}
```