メモ化再帰小技
AOJのTLE厳しいです…
ということでメモ化再帰だと少しだけTLEする、
あるいはTLEが心配みたいな時の小技をメモ。
int solve(int pos){ if(pos == n) return hoge; if(memo[pos] != -1) return memo[pos]; // なんか処理 return memo[pos] = ret; }
みたいな処理を
int solve2(int); inline int solve(int pos){ if(pos == n) return hoge; if(memo[pos] != -1) return memo[pos]; return solve2(pos); } int solve2(int pos){ // なんか処理 return memo[pos] = ret; }
のようにします。
多分なんか処理の部分は変更なしで大丈夫なはず。
あら不思議、少し速くなって時々TLEを回避できます。
手動でインライン展開するよりだいぶ楽かと。