sucrose https://blog.hatena.ne.jp/sucrose/ 唯物是真 @Scaled_Wurm https://sucrose.hatenablog.com/ python 競技プログラミング 天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」｜paizaオンラインハッカソンLite 問題設定 \(n\)個の会社それぞれに、エンジニアの人数\(q\)と価格\(r\)が与えられる 会社をいくつか選んで契約した時に、エンジニアの人数の合計がある値\(m\)以上になるときの最小のコスト(価格の合計)を求める ただしそれぞれの会社の人数の一部だけを雇うことはできず、会社ごとにまとめて契約することしかできない 解法1 - 動的計画法 どうみてもナップザック問題だ！ということで動的計画法を書いてみたところテストケース7で3.5秒ぐらいかかってしまいました mugenenさんの採点結果… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsucrose.hatenablog.com%2Fentry%2F2014%2F08%2F02%2F235858" title="PythonでpaizaオンラインハッカソンLiteに挑戦した - 唯物是真 @Scaled_Wurm" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/s/sucrose/20140802/20140802010239.jpg Hatena Blog https://hatena.blog 2014-08-02 23:58:58 rich https://sucrose.hatenablog.com/entry/2014/08/02/235858 1.0 100%