benchmark of 10,000,000 number's input time ( yes 100 | ./a.out ) Optimization Flags | number |iostream| stdio ---------------------+------------+--------+------ CXXFLAGS="" | 100 | 9.830 | 3.664 CXXFLAGS="-O2 -Wall" | 100 | 10.006 | 3.831…

主に漸化式で与えられる問題を解くのに使われる動的計画法(DP)。DPとメモ化再帰の定義を、フィボナッチ数列を計算するプログラムを例にして考える。 /* 「フィボナッチ 再帰バージョン」 * フィボナッチ数列を漸化式の通りに実装したもの * この計算ではO(1.…

C++での解答例。 問題1 /* * JOI 2010 予選 問題1 C++解答例 by qnighy */ // 問題: // レシート // http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t1/2010-yo-t1.html // 豆知識: // iostreamは遅いので、僕はstdio.hを使っています。 // c…