aoj2439:Hakone
解法
'-'のやつは、存在しないものとして考えてよい。
各順位について、
「前回その順位にいたやつは、今回順位が上がったか、下がったか」
「今回その順位に来るやつは、前回より順位が上がったやつか、下がったやつか」
という2*2=4通りのうちどれかを選ぶdpをやっていく。
dp[i][j]:=前回i位以上であったやつらでi位までを埋めようとしたとき、埋まっていない箇所がj箇所であるような通り数
とする。
漸化式を書く気力がないので、はい。
O(N^3)のdpを書いたら、2つのキーが常に一致していたので、O(N^2)になった。
dp配列の添え字の+-1とかを考えるのがきつくて頭が死んだ。
面倒
