No.519

BitDP + メモ化再帰を使う.

残っている人の集合を $S = \{ s_i \}$ として, 残っている人でペアを作ったときの相性度の合計の最大値を $A(S)$ とすると,

$$A(S) = \max_{2 \geq i \geq \vert S \vert} A(S \setminus \{ s_1, s_i \})$$

となる.