Problem 254 めも

取り敢えず，解いた．
しかし，少し遅い．約20秒 (Core 2 Duo E8500).

もうすこし工夫して下限を求めるか，
探索方法を工夫するか，
の二択なのか？

追記 #1

ad hoc な工夫をして，約3秒になった．
しかし，もう少し綺麗な改良の方法はないのか？

追記 #2

C++ で配列使ったアルゴリズムで実装したら，約0.2秒になった．
計算結果の再利用をしまくって，かなり速くなった．

教訓

配列のサイズが大きすぎると，スタックにのらずに，セグフォになるらしい．
そういときは，newで動的に確保するべし，ってどっかで読んだ．
例えば，二次元配列の場合

int (* a)[10] = new int[N][10];

とすれば，動的に確保できるらしい．