らての精進日記

修行をします

aoj2439:Hakone

解法

'-'のやつは、存在しないものとして考えてよい。

各順位について、
「前回その順位にいたやつは、今回順位が上がったか、下がったか」
「今回その順位に来るやつは、前回より順位が上がったやつか、下がったやつか」
という2*2=4通りのうちどれかを選ぶdpをやっていく。
dp[i][j]:=前回i位以上であったやつらでi位までを埋めようとしたとき、埋まっていない箇所がj箇所であるような通り数
とする。

漸化式を書く気力がないので、はい。


O(N^3)のdpを書いたら、2つのキーが常に一致していたので、O(N^2)になった。
dp配列の添え字の+-1とかを考えるのがきつくて頭が死んだ。
面倒

コード

広告を非表示にする