- Quiz
- AC
参考にした解説
https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3
部分集合から部分集合を選ぶ全列挙★
http://perogram.hateblo.jp/entry/2019/12/06/021400
無限ループでRE
- rec関数で無限ループに入る箇所があり、REが起きていた
- return code 139なので、いつもの配列の範囲外アクセスだと思いこみ、配列をvectorに書き直して、アクセスを[]から.at()に書き換えていくも直らず
- 原因は、部分集合の中の部分集合列挙時、空集合を作ってしまうと同じrecを呼んでしまうからだった
- 画像をよく見ると、max memory: 11MBと表示されており、これは配列のエラーでは出ない
- この表示の場合は同じrecを呼び続けたスタックオーバーフローだろう
2021/03/13
- それから2年後、再訪
- dp[flag] : その集合で取れる最高点数として、集合の分割を全部試す。集合を分割する際、ありえない分割をしないことで（上記★）計算量がオーダーレベルで減る
- AC https://atcoder.jp/contests/dp/submissions/20855179
