AOJ2321 Butterfly - 足跡-sokuseki-

問題概要

$N$ 個の用事があり、 $i$ 個目の用事は時間が $M_i$ 区間拘束され、 $j$ 個目の区間は $s_j$ 時から $e_j$ 時である。また $i$ 個目の用事をすると満足度が $L_i$ 得られる。
時間がかぶらないように行う用事を決めるとき、得られる満足度の最大値を求めよ。

制約

$1 \le N \le 100$
$1 \le M_i \le 16$
$1 \le L_i \le 10^8$
$6 \le S_i < E_i \le 22$

解法

制約から、時間は16個しかないので

dp[i][j] := i個目の用事までするかしないか決めたときに拘束される時間がjの状態のときに得られる最大の満足度

とするbitDPをすると、状態は $N \times 2^{16}$ 個しかないので間に合う。
入力で $i$ 個目の用事の区間を受け取るときに、bitに変換しておく（ $6+j$ 時から $6+j+1$ 時まで拘束されるときに $j$ ビット目を1にする）と、遷移できるかどうかは&をとればわかるので楽になる。

AIZU ONLINE JUDGE: Code Review