提出番号 | 2250 |
---|---|

提出者 | shung11260 |

言語 | C++ |

提出日時 | 2019-10-05 16:50:32 |

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

結果 | AC |

点数 | 100% |

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

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

2 | AC | 100% | 2ms | 8336KB |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

```
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;
int inf = numeric_limits<int>::max();
int main() {
int N;
cin >> N;
vector<int> t(N);
for(int i=0; i<N; i++) {
cin >> t[i];
}
vector<vector<int> > a(N, vector<int>(N));
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
cin >> a[i][j];
}
}
vector<int> dp(1<<N, inf);
dp[0] = 0;
for(int bit=0; bit<(1<<N); bit++) {
for(int nsflg=0; nsflg<N; nsflg++) {
if(!(bit & 1<<nsflg)) {
int ti = t[nsflg];
for(int sdflg=0; sdflg<N; sdflg++) {
if(bit & 1<<sdflg) {
ti -= a[sdflg][nsflg];
}
}
dp[bit+(1<<nsflg)] = min(dp[bit+(1<<nsflg)], dp[bit]+ti);
}
}
}
cout << dp[(1<<N)-1] << endl;
return 0;
}
```