mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ yukicoder dp bitDP 問題 問題概要 数字を並び替えた時に、条件を満たし、もっとも得点を獲得できる時の得点を求める。 解法 数字の数の最大値が14である。数字をすべて並び替える解法だと、計算量が(n!)になるので、TLE。そのためには計算量を(2n)にしなければならない。そこで、どの数字を使っているかという集合を考える。そして考えている集合に対して、集合に含まれていない数字を集合に含まれる数字の末尾に付け加える。末尾に付け加えた数字により、スコアが増えるので、その時の集合のスコアの最大を更新していく。 実際には dp[mask] = max(dp[mask], dp[mask ^ (1 << i)] + sum) … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2016%2F08%2F08%2F205026" title="yukicoder No.357 品物の並び替え (Middle) - srupのメモ帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-08-08 20:50:26 rich https://mmxsrup.hatenablog.com/entry/2016/08/08/205026 1.0 100%