提出番号 | 2222 |
---|---|

提出者 | syawacha |

言語 | C++ |

提出日時 | 2019-04-05 17:11:43 |

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

結果 | AC |

点数 | 100% |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29 | AC | 100% | 13ms | 8144KB |

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

```
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const int inf = 1000000000;
int main(){
int N;
cin >> N;
int t[N];
for(int i=0;i<N;i++) cin >> t[i];
int a[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin >> a[i][j];
}
}
int dp[1 << N];
fill(dp,dp+(1<<N),inf);
dp[0] = 0;
for(int i=0;i<(1<<N);i++){
for(int j=0;j<N;j++){
if(!(i & (1 << j))){
int dt = 0;
for(int k=0;k<N;k++){
if(i & (1 << k)){
dt += a[k][j];
}
}
dp[i + (1 << j)] = min(dp[i + (1 << j)], dp[i] + t[j] - dt);
}
}
}
cout << dp[(1 << N) - 1] << endl;
return 0;
}
```