No.357

No.90 の制限が厳しいバージョンである.

$N$ の最大値が $14$ なので全探索だと間に合わない. そこで BitDP を使う.

残りの荷物の集合を $A$, 荷物 $i$ が荷物 $j$ より前にあったときのスコアを $S(i, j)$, $A$ を並べたときに獲得できるスコアの最大値を $V(A)$ とすると,

$$V(A) = \max_{i \in A} \left( \sum_{j \in (A \setminus i)} S(i,j) + V(A \setminus i) \right)$$

となる.