提出番号 | 2239 |
---|---|

提出者 | ogma |

言語 | C++ |

提出日時 | 2019-07-11 16:41:43 |

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

結果 | AC |

点数 | 100% |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29 | AC | 100% | 15ms | 7920KB |

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

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int t[n],i,j,k;
for(i = 0; i < n;i++){
cin >> t[i];
}
int a[n][n];
for(i = 0; i < n;i++){
for(j = 0; j < n;j++){
cin >> a[i][j];
}
}
int dp[1 << n];
for(i = 0; i < 1 << n;i++){
dp[i] = 10000000;
}
dp[0] = 0;
for(i = 1; i < 1 << n;i++){
for(j = 0; j < n;j++){
if(i>>j &1){
int tmp = t[j];
for(k = 0; k < n; k++) {
if(k == j) continue;
if(i >> k & 1) tmp -= a[k][j];
}
dp[i] = min(dp[i], dp[i ^ (1 << j)] + tmp);
}
}
}
cout << dp[(1 << n) - 1] << endl;
return 0;
}
```