mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ yukicoder bitDP 順列 全探索 問題 問題概要 もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。 解法 すぐbitDPだろうなというのはわかる。ただ、どうやって、実装するかわからん。箱を使う最小値を求めればいいのだから、箱は大きいものから使用していけばいいことは自明。よって、おもちゃを箱に入れていく順番が重要？dpの状態として、いれたおもちゃの集合と大きい箱から何個目の箱までを使ったかをメモっておけば、その集合内で、どのような順番で箱におもちゃを入れたかはそのあとの解に影響を与えることはないので、bitDPできそう？ よくあるbitDP問題は、n=16などであり、(n!)解法の全探索を許さないが、今回… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2016%2F09%2F15%2F205709" title="yukicoder No.50 おもちゃ箱 - 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-09-15 20:57:09 rich https://mmxsrup.hatenablog.com/entry/2016/09/15/205709 1.0 100%