提出番号 | 2251 |
---|---|

提出者 | shung11260 |

言語 | C++ |

提出日時 | 2019-10-07 15:10:17 |

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

結果 | AC |

点数 | 100% |

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

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

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

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

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

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

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

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

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

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

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

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

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

13 | AC | 100% | 3ms | 8128KB |

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

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

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

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

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

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

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

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

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

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

24 | AC | 100% | 5ms | 8560KB |

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

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

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

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

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

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

```
#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> dp((1<<N), inf);
vector<int> t(N);
for(int i=0; i<N; i++) {
cin >> t[i];
}
vector<vector<int> > a(N, vector<int>(N, 0));
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
cin >> a[i][j];
}
}
dp[0] = 0;
for(int bit=0; bit<(1<<N); bit++) {
for(int flg=0; flg<N; flg++) {
if(~bit & (1<<flg)) {
int T=t[flg];
for(int i=0; i<N; i++) {
if(bit & (1<<i)) {
T -= a[i][flg];
}
}
dp[bit+(1<<flg)] = min(dp[bit+(1<<flg)], dp[bit]+T);
}
}
}
cout << dp[(1<<N)-1] << endl;
return 0;
}
```