提出番号 | 2190 |
---|---|

提出者 | toof |

言語 | C++ |

提出日時 | 2018-12-06 21:28:15 |

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

結果 | AC |

点数 | 100% |

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

1 | AC | 100% | 3ms | 0KB |

2 | AC | 100% | 2ms | 0KB |

3 | AC | 100% | 3ms | 0KB |

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

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

6 | AC | 100% | 8ms | 0KB |

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

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

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

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

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

12 | AC | 100% | 15ms | 0KB |

13 | AC | 100% | 31ms | 0KB |

14 | AC | 100% | 12ms | 0KB |

15 | AC | 100% | 16ms | 0KB |

16 | AC | 100% | 5ms | 0KB |

17 | AC | 100% | 3ms | 0KB |

18 | AC | 100% | 3ms | 0KB |

19 | AC | 100% | 66ms | 0KB |

20 | AC | 100% | 69ms | 0KB |

21 | AC | 100% | 4ms | 0KB |

22 | AC | 100% | 110ms | 0KB |

23 | AC | 100% | 8ms | 0KB |

24 | AC | 100% | 302ms | 0KB |

25 | AC | 100% | 51ms | 0KB |

26 | AC | 100% | 128ms | 0KB |

27 | AC | 100% | 288ms | 0KB |

28 | AC | 100% | 66ms | 0KB |

29 | AC | 100% | 1209ms | 0KB |

30 | AC | 100% | 147ms | 0KB |

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
int main() {
cin.tie(0); ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> t(n);
rep(i, n) cin >> t[i];
vector<vector<int>> a(n, vector<int>(n));
rep(i, n) rep(j, n) cin >> a[i][j];
int dp[1<<16];
rep(i, 1<<n) dp[i] = 1000*16+100;
dp[0] = 0;
rep(mask, 1<<n) {
rep(i, n) {
if (mask & 1<<i) continue;
int tmp = t[i];
rep(j, n) {
if (mask & 1 << j) tmp -= a[j][i];
}
cerr << bitset<3>(mask) << endl;
cerr << bitset<3>(mask+1<<i);
dp[mask+(1<<i)] = min(dp[mask+(1<<i)], dp[mask]+tmp);
}
}
cerr << endl;
rep(i, 1<<n) {
cerr << bitset<3>(i) << endl;
cerr << dp[i] << endl;
}
cerr << (1<<n)-1 << endl;
cout << dp[(1<<n)-1] << endl;
}
```