各宝箱が開いていない状態を 0, 開いている状態を 1 とするビット列を考える. 各鍵で開けられる宝箱も \(c_{ij}\) の \(j\) ビット目を 1 とするビット列とする. こうすることで鍵 \(i\) を使って宝箱を開けるということは宝箱の状態のビット列と鍵のビット列の OR を取ることで表せる.

\(i\) 番目の鍵まで見たときに宝箱の状態が \(j\) となるときの最小の費用を \(C(i, j)\) として,

\[\begin{align} C(i+1, j \lor Ki) &\leftarrow C(i, j) + a_i \\ C(i+1, j) &\leftarrow C(i, j) \end{align}\]

の要領で DP を使って更新していく. ただし, \(\leftarrow\) は左辺と右辺の最小値を取って左辺を置き換える操作である.