ARC132 C - Almost Sorted (600)
$ dp[i][j] をi番目まで見てjが使った数の集合とすると$ \mathcal{O}(N 2^N)の空間が必要になってメモリに載らない
解説の解法
上の配列のjの方をn個全部ではなく上下d個ずつの計$ 2d + 1個に絞る
それ以下は全て使ってないといけないし、それ以上はその時点では使っていないため
$ \mathcal{O}(N 2^{2d+1})の空間計算量に落ちる
0番目については0番目の値として決めた値と0未満にあたるbitが全部利用済みのものが1通りあることになる
それ以降のi番目の要素について以下を行う
遷移前の状態pについて全探索して以下を行う
$ -dに該当する値が利用済みで無い場合は飛ばす
i番目から見ると$ -d-1になるので埋めることができないため
pをi番目の状態に合わせるためqをpを1bitずらしたものとする
$ a_i = -1の場合
$ a_iの値を$ i - dから$ i + dまで試す
qで$ a_iにあたるbitが立っていたら飛ばす
それより前に利用済みであるため
そうでないなら$ dp[i][q|(1<<idx)] += dp[i-1][p]
それ以外の場合
qで$ a_iにあたるbitが立っていたら飛ばす
それより前に利用済みであるため
そうでないなら$ dp[i][q|(1<<idx)] += dp[i-1][p]
遷移が$ \mathcal{O}(d)通りなので時間計算量は$ \mathcal{O}(dN 4^d)