あたまわるいので…
この問題に2週間以上アタマを悩ませたが
結局答えは分からず諦めた
ACCが43％以上とあって俺でもいけるかなと思ったけど甘かった
QUALITYが一切ないことを考慮すべきだったかもしれない
ACCが43％と高いのは優秀な人たちしか挑戦してないせいなのかもしれない
問題番号が若いわりに挑戦人数が少なすぎるし
MMINDを諦めて次に挑戦した問題
問題のタグにヒントというか実質答えだが
問題のタグは見ずに挑戦はした*1
www.spoj.comド典型DPだと一目で分かる形をしてるので
余裕でACは出来た*2が
問題はソコじゃなくて
メモ化することで計算量的にオッケーになる証明(?)みたいなのが全くできない、わからない、
理屈的にはおそらくこんなイメージ*3でメモ化が効くってことなんだろうけど
適当なサンプルがメモ化が効くからって任意のnについてもそうであるなんて言えることになるわけじゃないし
ちゃんとオーダーを算出できない限り、キョープロで強くなれるわけないんだよね・・・
これはカンタンにイメージできるくらいの難易度だから直感で典型DPってして公式を当てはめるがごとくパターンとして解くことができるけど
カンタンにイメージできないような問題のときに証明(導出?)できる力みたいなのが重要なんじゃなかろうかと、思ってる（知らんけど）
とにかくDP全く分からん！
